题目一

给定两个字符串str1和str2，再给定三个整数ic、dc和rc，分别代表插入、删除和替换一个字符的代价，返回将str1编辑成str2的最小代价。【举例]str1="abc",str2=“adc",ic=5,dc=3,rc=2从“abc“编辑成adc",把'b'替换成'd'是代价最小的，所以返回2str1=“abc",str2=“adc“，ic=5,dc=3,rc=100从“abc“编辑成“adc”,先删除”b',然后插入'd'是代价最小的，所以返回8str1=“abc"，str2="abc"，ic=5，dc=3，rc=2不用编辑了，本来就是一样的字符串，所以返回0

dp数组解决

首先先想dp[i][j]是是什么意思

i是str1 j是str2  dp[i][j]是 str1的前i位 变成 str2的前j位的代价 那也就是左下角出结果呗

那我们看一下每一个位置的依赖

dp[0][0] 相同代价就是0  要么代价就是一个替换代价  

这里一般情况 应该是 添加+删除>替换 代价的 如果添加+删除的代价比替换的代价还小 那完全可以不需要替换这个操作了 但是这种可能性不能不防啊

dp[0][j] 肯定是添加一个的代价

dp[i][0] 那肯定是删除i个的代价

然后常态化的呢? dp[i][j] 

如果i和j位置相同的话 那就直接等于dp[i-1][j-1]了 不需要任何新的操作

如果不同 dp[i-1][j-1]+一个替换的代价

或者 dp[i-1][j]+删除代价

就是先把i-1的给弄立整的

比如  abcdf  abcd  它的i-1和j是相同的 所以只要删一个就行了

或者 dp[i][j-1]+添加代价

比如  abcd   abcdf 那就只要再加一个就行了

(j-1 i-1 并不能说明j-1一定比i小 这里的含义是位置 也就是说j的前一个位置 和i的当前位置相等 甚至再极端一点 i可能是2 j可能是10呢    ab  abcdefghij   它的依赖就走了dp[2][9]的值 每个格子只解决相邻的问题就行 虽然这个dp[2][10]的这个子问题并不能直接解决这个问题 甚至可以说与原问题(abcdefghi和abcdefghij)毫无干系  但是它作为可以填满整张表的basecase )

我刚开始是这么写的: 

 public static int MinPath(String str1,String str2,int ic,int dc,int rc) {char [] chars1 = str1.toCharArray();char [] chars2 = str2.toCharArray();int [][] dp = new int [chars1.length][chars2.length]; dp[0][0] = chars1[0]==chars2[0]?0:Math.min(rc,ic+dc);for(int i = 1;i<chars1.length;i++) {dp[i][0] = dp[i-1][0]+dc;}for(int i = 1;i<chars2.length;i++) {dp[0][i] = dp[0][i-1]+ic;}for(int i = 1;i<chars1.length;i++) {for(int j = 1;j<chars2.length;j++) {int p1 = dp[i-1][j-1]+rc;if(chars1[i] == chars2[j]) {p1 = dp[i-1][j-1];}int p2 = Math.min(dp[i-1][j]+dc, dp[i][j-1]+ic);dp[i][j] = Math.min(p1, p2);}}return dp[chars1.length-1][chars2.length-1]; }

但是在面对

例子的时候其实basecase是错的 当dp[1][2]的时候  chars1[1] chars2[2] 相等所以满足 p1 = dp[i-1][j-1];   dp[0][1] 是什么 a变成fa的最小代价 是先替换一个 再增加一个 这很明显是不对的 我们的最优解应该是 直接加上一个  这种情况是差在哪了呢 差在没考虑当str1为空的时候 比如a f的最佳选择虽然是替换或者删除再添加 那么a->fa的选择 也就被限制在了 先把第一位解决了 再解决后面的

在常态化的时候确实是这个理 但是实际上啊 实际上 我们是忽略掉了 str1a前面的一位 也就是说实际上是可以在a的前面加d 所以实际上我们的dp数组应该大一圈才对

不光是这个原因 还有特殊情况的考虑 如果一个字符串为空呢 对不对 与其搞两个if 不如直接写进dp

har [] chars1 = str1.toCharArray();char [] chars2 = str2.toCharArray();int [][] dp = new int [chars1.length][chars2.length]; dp[0][0] = chars1[0]==chars2[0]?0:Math.min(rc,ic+dc);for(int i = 1;i<chars1.length;i++) {dp[i][0] = dp[i-1][0]+dc;}for(int i = 1;i<chars2.length;i++) {dp[0][i] = dp[0][i-1]+ic;}for(int i = 1;i<chars1.length;i++) {for(int j = 1;j<chars2.length;j++) {int p1 = dp[i-1][j-1]+rc;if(chars1[i] == chars2[j]) {p1 = dp[i-1][j-1];}int p2 = Math.min(dp[i-1][j]+dc, dp[i][j-1]+ic);dp[i][j] = Math.min(p1, p2);}}return dp[chars1.length-1][chars2.length-1]; 

另外的 这题每个格子只依赖于 上一个格子或者前一个格子 可以进行优化

而且可以进行 旋转矩阵来保证最优空间(注意转置矩阵后 插入行为和删除行为有变动)

题目二

给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

刚开始想的是 能不能a 怎么删都变不了 b 结果人家说 a 和 b 全删没就行

 public int minDistance(String word1, String word2) {if(word1==word2) {return 0;}if(word1==null) {return word2.length();}if(word1==null) {return word1.length();}char [] chars1 = word1.toCharArray();char [] chars2 = word2.toCharArray();int N = chars1.length;int M = chars2.length;int [][] dp = new int [N][M];bofor(int i = 0;i<N;i++) {dp[i][0] = chars1[i] == chars2[0]?i:-1;}for(int i = 1;i<M;i++) {dp[0][i] = chars1[0] == chars2[i]?i:-1;}for(int i = 1;i<N;i++) {for(int j = 1;j<M;j++) {if(chars1[i]==chars2[j]) {if(dp[i][j-1]==-1&&dp[i-1][j]==-1) {dp[i][j] = i+j;}else {dp[i][j]=dp[i-1][j-1];}}else {if(dp[i][j-1]==-1&&dp[i-1][j]==-1) {dp[i][j] = -1;}else if(dp[i][j-1]==-1||dp[i-1][j]==-1){dp[i][j]=dp[i][j-1]==-1?dp[i-1][j]+1:dp[i][j-1]+1;}else {dp[i][j]=Math.min(dp[i][j-1], dp[i-1][j])+1;}}}}return dp[N-1][M-1];   }

这是刚开始的做法 寄了

 public int minDistance2(String word1, String word2) {char [] chars1 = word1.toCharArray();char [] chars2 = word2.toCharArray();int N = chars1.length+1;int M = chars2.length+1;int [][] dp = new int [N][M];for(int i = 1;i<N;i++) {dp[i][0] = i;}for(int i = 1;i<M;i++) {dp[0][i] = i;}for(int i = 1;i<N;i++) {for(int j = 1;j<M;j++) {if(chars1[i-1]==chars2[j-1]) {dp[i][j] = dp[i-1][j-1];}else {dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+1;}}}return dp[N-1][M-1];   }

这个的做法呢 是像上一题一样 多包涵了一圈 也就是加入了字符串为空的可能 所以basecase就有了删除到底的可能性了 然后dp[i][j] 如果字符串1的i位置和字符串2的j位置相等 那就不用删了 他就直接等于dp[i-1][j-1]  要么不等那就是dp[i-1][j]和dp[i][j-1]哪个小 再+1 也就是说 这个删除要么是str1删掉一个 要么是str2删掉一个 每次以1为步过 不用不相同时判断dp[i-1][j-1]的情况 因为已经包含在dp[i-1][j]和dp[i][j-1]的判断中了

看人家的题解说是 最长公共子序列 有道理 把最长公共子序列的剩余部分删掉就是结果了