两个字符串，二维表示状态

583. 两个字符串的删除操作

class Solution {
public:
    // 寻找最长公共串
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        vector<vector<int>> dp(n1 + 1, vector<int> (n2 + 1));
        for (int i = 1; i <= n1; i ++)
            dp[i][0] = i;
        for (int i = 1; i <= n2; i ++)
            dp[0][i] = i;
        for (int i = 1; i <= n1; i ++)
        {
            for (int j = 1; j <= n2; j ++)
            {
                if (word1[i-1] == word2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else
                {
                    dp[i][j] = min(min(dp[i-1][j] + 1, dp[i][j-1] + 1), dp[i-1][j-1] + 2);
                }
            }
        }
        return dp[n1][n2];
    }
};

72. 编辑距离

当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；

当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。

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