LeetCode 编辑距离 II（DP）

示例：
输入：s = "abcdefg", t = "abdde"
输出：3

提示：
1 <= len(s), len(t) <= 200

class Solution {
public:
    int edit_distance(string s, string t) {
        int n1 = s.size(), n2 = t.size();
        vector<vector<int>> dp(n1+1, vector<int>(n2+1, INT_MAX));
        for(int i = 0; i <= n1; ++i)
            dp[i][0] = i;//i个s字符变成0个t字符，需要删除次数
        for(int i = 0; i <= n2; ++i)
            dp[0][i] = i;
        for(int i = 1; i <= n1; ++i)
        {
            for(int j = 1; j <= n2; ++j)
            {
                if(s[i-1] == t[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                {
                    dp[i][j] =  dp[i-1][j-1]+1;//替换s或t的字符
                    if(i-1 >= j)//因为不能插入字符，删除 s 的 i 字符，前提是 s 字符串长度不能短于 t, 否则没有意义
                        dp[i][j] = min(dp[i][j], dp[i-1][j]+1);
                    if(j-1 >= i)//因为不能插入字符，删除 t 的 j 字符，前提是 t 字符串长度不能短于 s, 否则没有意义
                        dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
                }
            }
        }
        return dp[n1][n2];
    }
};