题解 | #牛群编号变更#

考察的知识点：动态规划；

解答方法分析：

1. 定义一个二维数组dp，其中dp[i][j]表示将s1的前i个字符变更为s2的前j个字符所需的最少操作次数。
2. 初始化dp数组的第一行和第一列，即dp[0][j]和dp[i][0]，对应于将空字符串变更为s2的前j个字符和将s1的前i个字符变更为空字符串，所需的操作次数就是对应的字符数量。
3. 从s1的第一个字符开始遍历到末尾，对于每个字符s1[i]，再从s2的第一个字符遍历到末尾，对于每个字符s2[j]，分为以下几种情况：如果s1[i]等于s2[j]，即当前字符相等，那么不需要进行任何操作，dp[i][j]等于dp[i-1][j-1]，即前一个字符的操作次数。如果s1[i]不等于s2[j]，即当前字符不相等，可以考虑进行删除操作或者插入操作：a) 删除操作：将s1的前i个字符删除一个字符，即dp[i][j]等于dp[i-1][j]+1，表示删除s1的第i个字符。b) 插入操作：在s1的第i个字符后面插入一个字符，使得s1的前i+1个字符等于s2的前j个字符，即dp[i][j]等于dp[i][j-1]+1，表示插入s2的第j个字符。
4. dp[s1.length()][s2.length()]的值即是所需的最少操作次数。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param word1 string字符串
     * @param word2 string字符串
     * @return int整型
     */
    int minDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
};