leetcode每日一题30

72. 编辑距离

动规啊，头大
动规五部曲走起

1. 确定dp数组（dp table）以及下标的含义
   dp[i][j]表示A[i-1]与B[j-1]的最近编辑距离
   （这么写是方便初始化）
2. 确定递推公式

if(word1[i-1]==word2[j-1])
	不变
else//此时word1[i-1]和word2[j-1]的字符不一样
	增
	删
	改
1
2
3
4
5
6

当word1和word2在长度为i-1、j-1时的字符相同的时候，相当于编辑距离等同于长度为i-2、j-2的时候的编辑距离，因此dp[i][j]=dp[i-1][j-1]
当word1和word2在长度为i-1时的字符不同时，

• 增：若word1比word2多一个字符，则word1删除一个，此时的编辑距离相当于word1长度为i-2，而word2长度为j-1时的编辑距离再加上1（因为要在word1[i-2]的基础上编辑一个），此时dp[i][j]=dp[i-1][j]+1;（注意，此情况等同于word2增加一个距离）
• 删：若word2比word1多一个字符，则word2删除一个，此时的编辑距离相当于word1长度为i-1，而word2长度为j-2时的编辑距离再加上1（因为要在word2[j-2]的基础上编辑一个），此时dp[i][j]=dp[i][j-1]+1;
• 改：若word2需要改成和word1一样的字符，那么此时编辑距离相当于word1长度为i-2，word2长度为j-2时的编辑距离+1，因此dp[i][j]=dp[i-1][j-1]+1；

所以当word1[i-1]!=word2[j-1]时，计算增删改哪个的长度最小，极为dp[i][j]

if(word1[i-1]==word2[j-1])
	dp[i][j]=dp[i-1][j-1];
else//此时word1[i-1]和word2[j-1]的字符不一样
	dp[i][j]=min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1});
1
2
3
4

3. 递归数组初始化
   根据dp数组的定义，初始化dp[0][j]和dp[i][0]
   dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。
   那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;
   同理dp[0][j] = j;

for (int i = 0; i <= word1.size(); i++) 
	dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) 
	dp[0][j] = j;
1
2
3
4

4. 确定遍历顺序
   从i-1 j-1计算到i j
   因此从上至下，从左至右遍历

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//此时word1[i-1]和word2[j-1]的字符不一样
			dp[i][j]=min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1});
1
2
3
4
5
6