题解 | #牛群的融合计划# 动态规划

********编辑距离：https://leetcode.cn/problems/edit-distance/description/

定义：dp[i][j] 为 breed1 的前 i 个字符转成 breed2 的前 j 个字符所需的距离

初始化：当 i 为 0 时，易知需要 j 的操作次数，即 dp[0][j] = j；同理，dp[i][0] = i

递推公式：从 str1 转成 str2 可以有以下三种方法：

1、在 str1 末尾插入一个字符，此时 str1[0...i]==str2[0...j-1]，那么对于 str2 的第 j 个字符，需要在 str1 的末尾插入该字符，对应 dp[i][j] = dp[i][j-1] + 1

2、在 str2 末尾插入一个字符，此时说明 str1[0...i-1]==str2[0...j]，那么对于 str1 的第 i 个字符，需要在 str2 的末尾插入该字符，对应 dp[i][j] = dp[i-1][j] + 1

3、修改 str1 的末尾字符，对应 dp[i][j] = dp[i-1][j-1] + 1

特别地，如果 str1 的末尾字符恰好与 str2 的末尾字符相同，那么可以不再需要操作，对应 dp[i][j] = dp[i-1][j-1]

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

时间复杂度：O(mn)，m和n分别为两个字符串的长度

空间复杂度：O(mn)，m和n分别为两个字符串的长度