题目描述

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
1.插入一个字符
2.删除一个字符
3.替换一个字符

样例

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

(DP)

word1和word2对操作枚举会超时滴，这幂次的操作数提示使用DP来解决

怎么考虑呢

先看看暴力枚举怎么写呢：
1. 要考虑枚举word1还是word2
2. 要考虑选中字符串进行增删改的操作的下标是哪个
3. 要考虑枚举的是哪一个操作

由此模拟下几个例子：
考虑单个字符串对其进行增删改：
例如字符串 要修改的串“abc”，要匹配的串”abxc“ ，

先随便增加字符k,增加到第一个位置，再把它删掉，这样只会徒增操作数，与目标串逆行。
同理先把字符c换成x，再把它换回来，也是无效的操作，增加操作数

这里定义一个概念：有效，指的是通过操作后和目标串的模式更接近了，由此得出所有无效的操作只会远离目标串增加操作数。

先删除c再加上x 以及 先加上x再删除c 两个方式执行顺序不同，但效果相同，关键是操作数也一样

既然如此，对一次有效的操作（可以增或删或改都视为有效的话），无论是目前选择哪一种操作都能更加接近目标，我们就人为定一个顺序：即每次有效操作之后（只有每次有效，整体有效，方案才是最优滴），被操作的字符不需要再进行改动，因为对它的操作是有效的，如果需要之后将其改动，则必然现在的操作是无效的，这与每次都是有效操作违背，所以顺序就这样引出来了：即从左往右扫，每次只考虑最后一位字符否可以进行有效的操作，这样不会对结果产生影响，也缩小了操作的范围（最后一个字符）。

好了到目前已经大体考虑了一部分，开始从集合角度分析DP问题吧（闫氏DP）~

由于是两个字符串，每次获取到这两个字符串的下标就可以对他们进行修改，因此状态的表示用两维f[i,j],它表示的是从字符串a前i位（1 ~ i）变成（通过若干操作后） 字符串b前j位（1 ~ j）的所有方案的集合。f代表经过操作数量的最小值
三种操作，两个字符串。可以将整个集合划分成3 * 2 种不同的子集
即：
对于a:
1. 在最后一位增加一个字符
2. 删除最后一个字符
3. 将最后一位字符替换

对于b：
1. 在最后一位增加一个字符
2. 删除最后一个字符
3. 将最后一位字符替换

从定义出发：f[i,j]表示a[1~i]和b[1~j]已经匹配了。
1. 对于第一类即在最后一位增加一个字符：
意思是 a 的前 i 位和 b 的前 j-1 位已经匹配了，只要再在a的末尾添一个字符：f[i,j-1] + 1
意思是 b 的前 j 位和 a 的前 i 位已经匹配了，只要再在b的末尾添一个字符：f[i-1,j] + 1
2. 对于第二类即删除最后一个字符：
意思是 a 的前 i-1 位和 b 的前 j 位已经匹配了，只要再删除a的末尾字符：f[i-1,j] + 1
意思是 b 的前 j-1 位和 a 的前 i 位已经匹配了，只要再删除b的末尾字符：f[i,j-1] + 1
3.对于第三类即将最后一位字符替换：
意思是 a 的前 i-1 位和 b 的前 j-1 位已经匹配了，只要再替换掉a的末尾字符：f[i-1,j-1] + 1
意思是 b 的前 j-1 位和 a 的前 i-1 位已经匹配了，只要再替换掉a的末尾字符：f[i-1,j-1] + 1
这里的末尾也有可能相等 即 ： 整个串都匹配了 f[i-1][j-1] = f[i][j]

综上：子集的表示方法：
1. f[i - 1][j - 1] + (a[i] != b[j])
2. f[i - 1][j] + 1
3. f[i][j - 1] + 1

之后就是对所有子集取一个Min得到最小的操作数

初始化：
空集 a ，串b，必然通过 a添加b.size()个字符 或 b删除b.size()个字符是最小的操作数；
空集 a, 空集 b，一次也不用操作，本来就是一样的

C++ 代码

class Solution {
public:
    int minDistance(string a, string b) {
        int n = a.size(), m = b.size();
        if(!m || !n)return n + m;
        a = " " + a, b = " " + b;
        vector<vector<int>> f(n + 1,vector<int>(m + 1,1e8));
        f[0][0] = 0;
        for(int i = 1; i <= n; i ++) f[i][0] = i;
        for(int i = 1; i <= m; i ++) f[0][i] = i;

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                f[i][j] = min(f[i][j],f[i - 1][j - 1] + (a[i] != b[j]));
                f[i][j] = min(f[i][j], f[i - 1][j] + 1);
                f[i][j] = min(f[i][j], f[i][j - 1] + 1);
            }
        return f[n][m];
    }
};