DP笔记(7)：DP从二维到多维解题
Author：zhoulujun Date：
编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符
示例 1：输入：word1 = "horse", word2 = "ros" 输出：3
解释：horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
编辑距离是用动规来解决的经典题目（没有了解动态规划的话，会感觉超级复杂）
编辑距离解题思路
使用动规五部曲，对本题做一个详细的分析：
确定dp数组（dp table）以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
有同学问了，为啥要表示下标i-1为结尾的字符串呢，为啥不表示下标i为结尾的字符串呢？
为什么这么定义，请请参看《DP笔记(4)：二维线性DP问题，从回文字串到子序列问题模板》里面的 718. 最长重复子数组 (opens new window)中做了详细的讲解。
其实用i来表示也可以！ 用i-1就是为了方便后面dp数组初始化的。
确定递推公式
在确定递推公式的时候，首先要考虑清楚编辑的几种操作，整理如下：
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 = "a"，word1删除元素'd' 和 word2添加一个元素'd'，变成word1="a", word2="ad"， 最终的操作数是一样！ 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;
}dp数组如何初始化
再回顾一下dp[i][j]的定义：
dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
那么dp[i][0] 和 dp[0][j] 表示什么呢？
dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。
那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;
同理dp[0][j] = j;
所以C++代码如下：
for (int i = 0; i <= word1.size(); i++) dp[i][0] = i; for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
确定遍历顺序
从如下四个递推公式：
dp[i][j] = dp[i - 1][j - 1]
dp[i][j] = dp[i - 1][j - 1] + 1
dp[i][j] = dp[i][j - 1] + 1
dp[i][j] = dp[i - 1][j] + 1
可以看出dp[i][j]是依赖左方，上方和左上方元素的，如图：
所以在dp矩阵中一定是从左到右从上到下去遍历。
for (int i = 1; i <= word1.size(); i++) {
for (int j = 1; j <= word2.size(); j++) {
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;
}
}
}最终代码
const minDistance = (word1, word2) => {
let dp = Array.from(Array(word1.length + 1), () => Array(word2.length+1).fill(0));
/**
* d e f
* |0|x|x|x|
* a |1|x|x|x|
* b |2|x|x|x|
* c |3|x|x|x|
*/
for(let i = 1; i <= word1.length; i++) {
dp[i][0] = i;
}
/**
* d e f
* |0|1|2|3|
* a |x|x|x|x|
* b |x|x|x|x|
* c |x|x|x|x|
*/
for(let j = 1; j <= word2.length; j++) {
dp[0][j] = j;
}
/**
* 上面两个操作后，求解矩阵变为
* d e f
* |0|1|2|3|
* a |1|x|x|x|
* b |2|x|x|x|
* c |3|x|x|x|
* 接下来就是填充剩余表格
*/
for(let i = 1; i <= word1.length; i++) {
for(let j = 1; j <= word2.length; j++) {//i = 1,j = 1, 2, 3，以行开始填充
if(word1[i-1] === word2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1);
}
}
}
return dp[word1.length][word2.length];
};参考文章：
https://writings.sh/post/algorithm-minimum-edit-distance
https://programmercarl.com/0072.编辑距离.html
经典动态规划：编辑距离 https://www.cxyxiaowu.com/10220.html
8.动态规划（1）——字符串的编辑距离 https://www.cnblogs.com/yulinfeng/p/7096882.html
转载本站文章《DP笔记(7)：DP从二维到多维解题》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9117.html