建设网站用什么好处,摄影网站在线建设,免费开店的平台,如何利用php开源系统建立php网站Day 50 动态规划 part16 解题理解58372 2道题目 583. 两个字符串的删除操作 72. 编辑距离
解题理解
583
dp[i][j]#xff1a;以i-1为结尾的字符串word1#xff0c;和以j-1位结尾的字符串word2#xff0c;想要达到相等#xff0c;所需要删除元素的最少次数。 当word1[i -… Day 50 动态规划 part16 解题理解58372 2道题目 583. 两个字符串的删除操作 72. 编辑距离
解题理解
583
dp[i][j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2想要达到相等所需要删除元素的最少次数。 当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。
class Solution:def minDistance(self, word1: str, word2: str) - int:l1 len(word1)l2 len(word2)dp [[0] * (l2 1) for _ in range(l1 1)]for i in range(l2 1):dp[0][i] ifor i in range(l1 1):dp[i][0] ifor i in range(1, l1 1):for j in range(1, l2 1):if word1[i - 1] word2[j - 1]:dp[i][j] dp[i - 1][j - 1]else:dp[i][j] min(dp[i][j - 1] 1, dp[i - 1][j] 1, dp[i - 1][j - 1] 2)return dp[-1][-1]72
dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。 if (word1[i - 1] word2[j - 1]) 那么说明不用任何编辑dp[i][j] 就应该是 dp[i - 1][j - 1]即dp[i][j] dp[i - 1][j - 1]; 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 “a”word1删除元素’d’ 和 word2添加一个元素’d’变成word1“a”, word2“ad” 最终的操作数是一样
操作三替换元素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;
class Solution:def minDistance(self, word1: str, word2: str) - int:l1 len(word1)l2 len(word2)dp [[0] * (l2 1) for _ in range(l1 1)]for i in range(l2 1):dp[0][i] ifor i in range(l1 1):dp[i][0] i for i in range(1, l1 1):for j in range(1, l2 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][j - 1], dp[i - 1][j]) 1return dp[-1][-1]
