每天一道leetcode：72. 编辑距离（动态规划困难）

今日份题目：

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例1

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例2

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

题目思路

动态规划，将整个单词的编辑问题转换成三个子问题的编辑问题。

思路：插入、删除、替换三个操作可以在word1和word2两个单词中分别操作，并且，word1的插入操作就是word2的删除操作，同理，word2的插入操作就是word1的删除操作，所以，双方的六个操作可以简化为word1的插入操作、word2的插入操作和替换操作三个操作。假设当前位置是word1的第i个字符、word2的第j个字符。所谓word1的插入操作，就是在i-1和j的位置的基础上，也就是word1的前i-1个字符和word2的前j个字符编辑的距离的子问题下对word1进行插入操作；所谓word2的插入问题，就是在i和j-1的位置的基础上，也就是word1的前i个字符和word2的前j-1个字符编辑的距离的子问题下对word2进行插入操作；所谓替换操作，就是在i-1和j-1的位置的子问题下对当前字符进行判断是否需要替换，如果字符不同就需要替换，相同就不需要替换，注意，dp中的i是word中的i-1，因为word从0开始遍历下标，dp从1开始遍历下标。

接下来就是大家比较关心的状态转移方程问题：

根据上段的分析，我们知道，会有三种状态（三种操作对应三种状态）：

//word1插入字符：word1的前i-1个字符和word2的前j个字符编辑的距离+本次word1插入1个字符
int a=dp[i-1][j]+1;
//word2插入字符：word1的前i个字符和word2的前j-1个字符编辑的距离+本次word2插入1个字符
int b=dp[i][j-1]+1;
//替换：word1的前i-1个字符和word2的前j-1个字符编辑的距离+本次替换字符
int c=dp[i-1][j-1];
if(word1[i-1]!=word2[j-1]) c+=1;
//如果word1的第i个字符（word的下标为i-1）和word2的第j个字符（word的下标为j-1）相同，就不需要进行替换修改操作

状态转移方程就是取操作后的最小状态（因为要求最小操作距离）：

dp[i][j]=min(a,min(b,c));

状态转移方程对比：

最后，dp [ n ] [ m ] 就是我们要返回的答案。

这道题目比较困难，思路也可能存在漏洞，欢迎大家在评论区进行讨论，谢谢！

代码

class Solution 
{
public:int minDistance(string word1, string word2) {//获取两个字符串的长度int n=word1.length();int m=word2.length();//有一个字符串为空串if(n==0) return m;else if(m==0) return n;//dp数组int dp[1000][1000]={0};//边界状态初始化for(int i=0;i<=n;i++) {dp[i][0]=i;//相对于word1执行i次删除操作}for(int j=0;j<=m;j++) {dp[0][j]=j;//相对于word1执行j次插入操作}//计算所有dp值for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {//word1的前i-1个字符和word2的前j个字符编辑的距离+本次：word1插入1个字符int a=dp[i-1][j]+1;//word1的前i个字符和word2的前j-1个字符编辑的距离+本次：word2插入1个字符int b=dp[i][j-1]+1;//word1的前i-1个字符和word2的前j-1个字符编辑的距离+本次：替换字符int c=dp[i-1][j-1];//如果word1的第i个字符（word的下标为i-1）和word2的第j个字符（word的下标为j-1）相同，就不需要进行替换修改操作if(word1[i-1]!=word2[j-1]) c+=1;dp[i][j]=min(a,min(b,c));}}return dp[n][m];}
};