新乡建站,温州百度推广排名优化,网站建设陕icp,济南网站设计开发文章目录 前言一、583. 两个字符串的删除操作二、72. 编辑距离三、动态规划之编辑距离总结篇总结 前言 一、583. 两个字符串的删除操作 两种思路#xff1a;1.直接动态规划#xff0c;求两个字符串需要删除的最小次数 2.采用子序列的和-最长公共子序列。思路一分析如下#… 文章目录 前言一、583. 两个字符串的删除操作二、72. 编辑距离三、动态规划之编辑距离总结篇总结 前言 一、583. 两个字符串的删除操作 两种思路1.直接动态规划求两个字符串需要删除的最小次数 2.采用子序列的和-最长公共子序列。思路一分析如下 动规五部曲分析如下 确定dp数组dp table以及下标的含义 dp[i][j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2想要达到相等所需要删除元素的最少次数。 这里dp数组的定义有点点绕大家要撸清思路。 确定递推公式 当word1[i - 1] 与 word2[j - 1]相同的时候当word1[i - 1] 与 word2[j - 1]不相同的时候 当word1[i - 1] 与 word2[j - 1]相同的时候dp[i][j] dp[i - 1][j - 1]; 当word1[i - 1] 与 word2[j - 1]不相同的时候有三种情况 情况一删word1[i - 1]最少操作次数为dp[i - 1][j] 1 情况二删word2[j - 1]最少操作次数为dp[i][j - 1] 1 情况三同时删word1[i - 1]和word2[j - 1]操作的最少次数为dp[i - 1][j - 1] 2 那最后当然是取最小值所以当word1[i - 1] 与 word2[j - 1]不相同的时候递推公式dp[i][j] min({dp[i - 1][j - 1] 2, dp[i - 1][j] 1, dp[i][j - 1] 1}); 因为 dp[i][j - 1] 1 dp[i - 1][j - 1] 2所以递推公式可简化为dp[i][j] min(dp[i - 1][j] 1, dp[i][j - 1] 1); 这里可能不少录友有点迷糊从字面上理解 就是 当 同时删word1[i - 1]和word2[j - 1]dp[i][j-1] 本来就不考虑 word2[j - 1]了那么我在删 word1[i - 1]是不是就达到两个元素都删除的效果即 dp[i][j-1] 1。 dp数组如何初始化 从递推公式中可以看出来dp[i][0] 和 dp[0][j]是一定要初始化的。 dp[i][0]word2为空字符串以i-1为结尾的字符串word1要删除多少个元素才能和word2相同呢很明显dp[i][0] i。 确定遍历顺序 从递推公式 dp[i][j] min(dp[i - 1][j - 1] 2, min(dp[i - 1][j], dp[i][j - 1]) 1); 和dp[i][j] dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。 所以遍历的时候一定是从上到下从左到右这样保证dp[i][j]可以根据之前计算出来的数值进行计算。 举例推导dp数组 代码思路一 关键代码 dp[i][j] Math.min(dp[i - 1][j - 1] 2, Math.min(dp[i - 1][j] 1, dp[i][j - 1] 1)); 优化代码 dp[i][j] Math.min(dp[i - 1][j] 1, dp[i][j - 1] 1); class Solution {public int minDistance(String word1, String word2) {int len1 word1.length();int len2 word2.length();int[][] dp new int[len11][len21];for(int i 1;ilen1;i){dp[i][0] i; }for(int j 1;jlen2;j){dp[0][j] j;}for(int i 1;ilen1;i){for(int j 1;jlen2;j){if(word1.charAt(i-1) word2.charAt(j-1)){dp[i][j] dp[i-1][j-1];}else{dp[i][j] Math.min(dp[i][j-1]1,dp[i-1][j]1);}}}return dp[len1][len2];}
}代码思路二
class Solution {public int minDistance(String word1, String word2) {int len1 word1.length();int len2 word2.length();int[][] dp new int[len11][len21];for(int i 1;i len1;i){for(int j 1;j len2;j){if(word1.charAt(i-1) word2.charAt(j-1)){dp[i][j] dp[i-1][j-1] 1;}else{dp[i][j] Math.max(dp[i-1][j],dp[i][j-1]);}}}return len1 len2 - 2*dp[len1][len2];}
} 二、72. 编辑距离 因为前面的铺垫这题显得并不困难难点在于理解另外本题的代码基本复制的上一题的解法一只更改了了一行代码 dp[i][j] Math.min(dp[i - 1][j - 1] 1, Math.min(dp[i - 1][j] 1, dp[i][j - 1] 1)); 因为题解基本一致这里只提及了最有差异的递推公式的解 确定递推公式 在确定递推公式的时候首先要考虑清楚编辑的几种操作整理如下 if (word1[i - 1] word2[j - 1])不操作
if (word1[i - 1] ! word2[j - 1])增删换也就是如上4种情况。 if (word1[i - 1] word2[j - 1]) 那么说明不用任何编辑dp[i][j] 就应该是 dp[i - 1][j - 1]即dp[i][j] dp[i - 1][j - 1]; 此时可能有同学有点不明白为啥要即dp[i][j] dp[i - 1][j - 1]呢 那么就在回顾上面讲过的dp[i][j]的定义word1[i - 1] 与 word2[j - 1]相等了那么就不用编辑了以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1]就是 dp[i][j]了。 在下面的讲解中如果哪里看不懂就回想一下dp[i][j]的定义就明白了。 在整个动规的过程中最为关键就是正确理解dp[i][j]的定义 if (word1[i - 1] ! word2[j - 1])此时就需要编辑了如何编辑呢 操作一word1删除一个元素那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。 即 dp[i][j] dp[i - 1][j] 1; 操作二word2删除一个元素那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。 即 dp[i][j] dp[i][j - 1] 1; 这里有同学发现了怎么都是删除元素添加元素去哪了。 word2添加一个元素相当于word1删除一个元素例如 word1 ad word2 aword1删除元素d 和 word2添加一个元素d变成word1a, word2ad 最终的操作数是一样 dp数组如下图所示意的 a a d---------- ---------------| 0 | 1 | | 0 | 1 | 2 |---------- ---------------a | 1 | 0 | a | 1 | 0 | 1 |---------- ---------------d | 2 | 1 |----------操作三替换元素word1替换word1[i - 1]使其与word2[j - 1]相同此时不用增删加元素。 可以回顾一下if (word1[i - 1] word2[j - 1])的时候我们的操作 是 dp[i][j] dp[i - 1][j - 1] 对吧。 那么只需要一次替换的操作就可以让 word1[i - 1] 和 word2[j - 1] 相同。 所以 dp[i][j] dp[i - 1][j - 1] 1; 综上当 if (word1[i - 1] ! word2[j - 1]) 时取最小的即dp[i][j] min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) 1; 递归公式代码如下 if (word1[i - 1] word2[j - 1]) {dp[i][j] dp[i - 1][j - 1];
}
else {dp[i][j] min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) 1;
}class Solution {public int minDistance(String word1, String word2) {int len1 word1.length();int len2 word2.length();int[][] dp new int[len11][len21];for(int i 1;ilen1;i){dp[i][0] i; }for(int j 1;jlen2;j){dp[0][j] j;}for(int i 1;ilen1;i){for(int j 1;jlen2;j){if(word1.charAt(i-1) word2.charAt(j-1)){dp[i][j] dp[i-1][j-1];}else{dp[i][j] Math.min(dp[i-1][j-1]1,Math.min(dp[i][j-1]1,dp[i-1][j]1));}}}return dp[len1][len2];}
}三、动态规划之编辑距离总结篇 考虑动态规划首先明确dp数组以及下标的含义如果是i-1j-1考虑一下好处随后是递推公式这里需要对两个字符串因为基本是字符串数组的前后操作进行思考接着进行初始化初始化会因为dp数组的含义不同而不同其次是根据递推公式确定遍历顺序因此最后一步打印dp数组也成为检验的重要一步。 总结
动态规划。
