网站后台查询软件,泰和网站制作,wordpress play主题,软文媒体发稿平台学习交流加 个人qq#xff1a; 1126137994个人微信#xff1a; liu1126137994学习交流资源分享qq群#xff1a; 962535112 对于两个字符串A和B#xff0c;我们需要进行插入、删除和修改操作将A串变为B串#xff0c;定义c0#xff0c;c1#xff0c;c2分别为三种操作的代价… 学习交流加 个人qq 1126137994个人微信 liu1126137994学习交流资源分享qq群 962535112 对于两个字符串A和B我们需要进行插入、删除和修改操作将A串变为B串定义c0c1c2分别为三种操作的代价请设计一个高效算法求出将A串变为B串所需要的最少代价。
给定两个字符串A和B及它们的长度和三种操作代价请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300且三种代价值均小于等于100。
测试样例 “abc”,3,“adc”,3,5,3,100 返回8
解题思路 假设A的长度为n,B的长度为m首先生成一个dp矩阵dp[n1]m1,dp[i][j]代表将A[0(i-1)]变成B[0(j-1)]的最小代价。 1、先求第一行 dp[0][j],将空串变成B[0…j-1],直接一个一个插入
for(int j0;jm1;j){dp[0][j]j*ic;//ic代表插入的操作的代价}2、再求第一列 将A[0…i-1]变成空串,直接一个一个删除
for(int i0;in1;i){dp[i][0]i*dc;//dc代表删除的操作代价}3、求其他行的值 求其他行的值可以大致分为以下四种情况
一、 先把A[0(i-1)]编辑成A[0(i-2)],也就是删除字符A[i-1],再将A[0(i-2)]编辑成B[0(j-1)]dp[i-1][j],所以 dp[i][j]dcdp[i-1][j]
二、 先把A[0(i-1)]编辑成B[0(j-2)],即dp[i][j-1],再将B[0~(j-2)]插入B[j-1],所以 dp[i][j]icdp[i][j-1]
三、 如果A[i-1]!B[j-1],那么先把A[0(i-2)]编辑成B[0(j-2)],然后把A[i-1]替换成B[j-1]即可所以 dp[i][j]rcdp[i-1][j-1];
四、 如果A[i-1]B[j-1]那么直接把A[0(i-2)]编辑成B[0(j-2)],即可所以 dp[i][j]dp[i-1][j-1];
选出以上四种情况的最小值就是最终dp[i][j]的值。
综上编写程序如下
class MinCost {
public:int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) {// write code hereint icc0,dcc1,rcc2;int dp[n1][m1];//先求第一行dp[0][j],将空串变成B[0...j-1],直接一个一个插入for(int j0;jm1;j){dp[0][j]j*ic;}//再求第一列将A[0...i-1]变成空串,直接一个一个删除for(int i0;in1;i){dp[i][0]i*dc;}//再求其他行,从上到下从左往右计算for(int i1;in1;i){for(int j1;jm1;j){int Min_Nummin(dcdp[i-1][j],icdp[i][j-1]);if(A[i-1]!B[j-1]){Min_Nummin(rcdp[i-1][j-1],Min_Num);}else{Min_Nummin(dp[i-1][j-1],Min_Num);} dp[i][j]Min_Num;}}return dp[n][m];}
};
