edit-distance

假设字符串 a, 共 m 位，从 a[1] 到 a[m]
字符串 b, 共 n 位，从 b[1] 到 b[n]
d[i][j] 表示字符串 a[1]-a[i] 转换为 b[1]-b[j] 的编辑距离

那么有如下递归规律（a[i] 和 b[j] 分别是字符串 a 和 b 的最后一位）：

当 a[i] 等于 b[j] 时，d[i][j] = d[i-1][j-1], 比如 fxy -> fay 的编辑距离等于 fx -> fa 的编辑距离
当 a[i] 不等于 b[j] 时，d[i][j] 等于如下 3 项的最小值：
d[i-1][j] + 1（删除 a[i]）， 比如 fxy -> fab 的编辑距离 = fx -> fab 的编辑距离 + 1
d[i][j-1] + 1（插入 b[j])， 比如 fxy -> fab 的编辑距离 = fxyb -> fab 的编辑距离 + 1 = fxy -> fa 的编辑距离 + 1
d[i-1][j-1] + 1（将 a[i] 替换为 b[j]）， 比如 fxy -> fab 的编辑距离 = fxb -> fab 的编辑距离 + 1 = fx -> fa 的编辑距离 + 1
递归边界：

1.a[i][0] = i, b 字符串为空，表示将 a[1]-a[i] 全部删除，所以编辑距离为 i
2.a[0][j] = j, a 字符串为空，表示 a 插入 b[1]-b[j]，所以编辑距离为 j

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1=word1.length(),len2=word2.length();
        vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));
        for(int i=0;i<=len1;i++)dp[i][0]=i;
        for(int j=0;j<=len2;j++)dp[0][j]=j;
        
        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;j++)
            {
                if(word1[i-1]==word2[j-1])
                    dp[i][j]=dp[i-1][j-1];
                else{
                    dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
                }
            }
        }
        return dp[len1][len2];
    }
};