经典动态规划：编辑距离 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：经典动态规划：编辑距离

评论礼仪 见这里，违者直接拉黑。

[CNLarryAn]

厉害了

[shiboys]

还真是楼主说的，看着很复杂，解起来很简单。
动态规划果然很厉害呀，需要细细品味，多多联系，反复咀嚼

[deepbreath373]

递归Java版（带备忘录）

class Solution {
    int[][] memo;
    public int minDistance(String word1, String word2) {
        memo = new int[word1.length()][word2.length()];
        return dp(word1, word2, word1.length()-1, word2.length()-1);
    }
    private int dp(String s1, String s2, int i, int j){
        if(i == -1) return j+1;
        if(j == -1) return i+1;
        if(memo[i][j] != 0) return memo[i][j];
        if(s1.charAt(i) == s2.charAt(j)){
            memo[i][j] = dp(s1,s2,i-1,j-1);
        }else{
            int a = dp(s1,s2,i,j-1) + 1;
            int b = dp(s1,s2,i-1,j) + 1;
            int c = dp(s1,s2,i-1,j-1) + 1;
            memo[i][j] = Math.min(a, Math.min(b, c));
        }
        return memo[i][j];
    }
}

[shiboys]

三个状态的版本呗？作者不是说了吗，可读性降低，本来他的那个版本可读性就已经很低了

[fornobugworld]

DP table版应该再初始一个dp[0][0]=0吧

[JiepingLi]

数组初始化默认就是0

[Nelsonlin0321]

其实插入等价于删除，在字符串1里插入P 等价于在字符串2删除对应的字符。操作只有删除和替换。

[zongxindu]

为什么呢？

[Nelsonlin0321]

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        
        max_distance = max(len(word1),len(word2))
        
        # base case
        if len(word1) * len(word2)==0:
            return max_distance
        
        
        #dp table
        row = [max_distance for _ in range(len(word2)+1)]
        dp = [row.copy() for _ in range(len(word1)+1)]
        
        dp[0][0] = 0
        
        # base case
        for i in range(len(word1)+1):
            dp[i][0] = i
        
        for j in range(len(word2)+1):
            dp[0][j] = j
        
        
        for i in range(1,len(word1)+1):
            for j in range(1,len(word2)+1):
                char_1 = word1[i-1]
                char_2 = word2[j-1]
                
                if char_1 == char_2:
                    # 相同的情况上，就不用操作，就等于上一个阶段
                    dp[i][j] = dp[i-1][j-1]
                else:
                    # 不相同的情况上，有三种操作的可能 1）删除左边 2） 删除右边 3）替换/  插入跟删除本质是同一个种操作
                    dp[i][j] = 1 + min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
        
        return dp[-1][-1]

[JackHo327]

东哥 有个图挂了

[labuladong]

@JackHo327 没有吧，应该是你网络问题

[MathsGo]

东哥，第三个大标题上面的大段代码，关于dp数组的定义，是不是不大对？

// 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i-1][j-1]

莫不是应该写成？

// 定义：s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离是 dp[i][j]

[labuladong]

@MathsGo 是我写错了，感谢指出~

[cmh1779]

class Solution {
public:        
    int memo[501][501];
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                memo[i][j] = 0;
        return dp(m,n, word1, word2);
    }
    int dp(int i, int j, string word1, string word2){
            if(memo[i][j]!=0)
                return memo[i][j];
            if(i==0) return memo[i][j] = j;
            if(j==0) return memo[i][j] =i;
            if(word1[i-1]==word2[j-1])
                memo[i][j] = dp(i-1,j-1, word1, word2);
            else
                 memo[i][j] = min(min(dp(i-1,j,word1,word2)+1,dp(i,j-1,word1,word2)+1),dp(i-1,j-1,word1,word2)+1);
            return memo[i][j];
    }
};

[zy159864]

#递归+备忘录--python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:

        help_dict={}
        def dp(i: int, j: int):

            if (i,j) in help_dict:
                return help_dict[(i,j)]
            #base case: word1没走完，word1全删掉，word2没走完，word1全插入
            if i == -1:
                return j+1
            if j == -1:
                return i+1
            
            if word1[i] == word2[j]:
                help_dict[(i,j)] = dp(i-1, j-1)      #本来就匹配的，i,j前移  

            else:
                
                help_dict[(i,j)] =  min(dp(i, j-1)+1,  #插入字符后，匹配了，但i不变，j左移
                                        dp(i-1,j)+1,   #删除字符后，i前移，j不变
                                        dp(i-1, j-1)+1)#替换字符后，匹配了，i前移，j也前移
            return help_dict[(i,j)]
        return dp(len(word1)-1, len(word2)-1)

[Pierce-Dai]

自底向上C++代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        int size1 = word1.size(), size2 = word2.size();
        vector<vector<int>> dp(size1 + 1, vector<int>(size2 + 1));
        //base case
        for(int i = 1; i<= size1; ++i)
            dp[i][0] = i;
        for(int j = 1; j <= size2; ++j)
            dp[0][j] = j;
            //自底向上求解
        for(int i = 1; i <= size1; ++i) {
            for(int j = 1; j <= size2; ++j) {
                if(word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = minAbc(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
            }
        }
        return dp[size1][size2];
    }

    int minAbc(int a, int b, int c) {
        return min(a, min(b, c));
    }
};

[SharkLJ]

递归解法的复杂度是多少？

[NealCou]

东哥，递归函数中插入的情况，“我直接在s1[i]插入一个和s2[j]一样的字符"，有点不理解；
根据动图，s1中插入新字母加后，s1[i]对应的字母没有变化，是不是这样表述更好“直接在s1[i+1]插入一个...”。

[morganwu277]

其实关于插入，一个更好的表述是：

因为 dp(i, j-1) 表示的是 s1和s2 经过 dp(i, j-1) 步骤已经变得一样了。
那对于 dp(i, j) 也就是，s2 从 j-1 的情况尾巴新增一个字符，长度变为j了，如何再令其变得一样呢？自然是在s1的尾巴插入一个字符啊。
所以从 dp(i, j-1) 转移过来，自然就是插入的case。

同理，从 dp(i-1, j) 转移过来的话，那自然就是对 s1的尾巴进行删除操作。

[labuladong]

@NealCou 嗯，你说的有道理，我修改一下表述

[zhongweiLeex]

交错字符串DP数组自下而上思路

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
        if(len1 + len2 != len3){
            return false;
        }
        //dp[i][j] 表示 s1[0..i-1] s2[0..j-1] 是否能平凑出 s3[0..i+j-1] 
        boolean[][] dp = new boolean[len1+1][len2+1];
        dp[0][0] = true;

        
        for(int i = 1; i<=len1;i++){
            //当前 s2 为空字符串的时候， 就需要看s3的字符是否与 s1 中的是否相同了 ， 如果相同， 则可以平凑出来
            if(s1.charAt(i-1) == s3.charAt(i-1)){
                dp[i][0] = dp[i-1][0] && true ;
            }else{
                dp[i][0] = false;
            }
        }
        for(int j = 1 ; j<=len2;j++){
            if(s2.charAt(j-1) == s3.charAt(j-1)){
                dp[0][j] = dp[0][j-1];
            }else{
                dp[0][j] = false;
            }
        }

        for(int i = 1; i<=len1;i++){
            for(int j = 1 ; j<=len2;j++){
                //当前s3 位置的可以靠  s1 可以凑出 ， 则当前位置的依靠前面的状态转换过来
                if(s1.charAt(i-1) == s3.charAt(i+j-1) ){
                    dp[i][j] = dp[i-1][j]; //当前位置i可以凑出来的， 那么就要看前面的i-1是否可以凑出来了
                }
                //同理
                if(s2.charAt(j-1) == s3.charAt(i+j-1)){
                    dp[i][j] = dp[i][j] || dp[i][j-1];
                }
            }
        }
        return dp[len1][len2];
    }
}

[MzxlM]

通过学习 对动态规划进行降维打击 写出的压缩数组 自顶向下java写法

    public int minDistance(String w1, String w2) {
        int r = w1.length()+1, c = w2.length()+1;
        
        int[] dp1 = new int[c];
        for(int i = 0; i < c; i++) {
            dp1[i] = i;
        }
    
        for( int i = 1; i < r; i ++) {
            int pre = i-1;
            dp1[0] = i;
            for ( int j = 1; j < c; j++) {
                int temp = dp1[j];
                if(w1.charAt(i-1) == (w2.charAt(j-1))) {
                    dp1[j] = pre;
                    // dp[i][j] = dp[i-1][j-1];
                } else {
                    dp1[j] = Math.min(Math.min(dp1[j], pre), dp1[j-1]) +1;
                    // dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i-1][j-1]), dp[i][j-1]) +1;
                }
                pre = temp;
            }
        }
        return dp1[c-1];
    }

[YEthYuan]

【Java版空间压缩代码供参考】 能力有限所以没有实现@dreamer2q 同学的严格O(min(M,N))空间复杂度，不过马虎一下毕竟还是把复杂度降低了一个数量级（

// 空间压缩版代码
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[] dp = new int[n + 1];
        for (int j = 0; j <= n; j++) {
            dp[j] = j;
        }
        for (int i = 1; i <= m; i++) {
            int pre = i - 1;
            dp[0] = i;
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[j] = pre;
                } else {
                    dp[j] = min(pre, dp[j], dp[j - 1]) + 1;
                }
                pre = temp;
            }
        }
        return dp[n];
    }

    private int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

[bruceeewong]

可以解释下 pre = i - 1, dp[0] = i 这里的初始化是怎么得来的不，谢谢

[Velliy]

1、根据定义正着解释，两个字符串都可以操作，删除和替换 2、根据作者的倒着来但是 函数的话就倒着解释，dp数组的话就正着解释，只操作s1，增加、插入和删除

[labuladong]

嗯，正着来和倒着来一样的，只要改改定义和状态转移的参数就行了

[SUN7700]

如果有跟我一样看的比较蒙的菜鸟，不知道为什么这样操作后就是正确结果，可以综合看看leetcode官方对这一题的题解。https://leetcode.cn/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/

[yonggui-yan]

打卡打卡
学到了
如果需要知道怎么编辑，则DP[i] = {距离，操作动作}.

[bruceeewong]

打卡，居然把3种操作抽象成下标移动，真的巧妙

[CarlLy7]

打卡，从顶到底的递归理解了，但是dp table理解的不到位，感觉有点难啊

[CarlLy7]

二刷打卡

[T-Macgrady]

学到了
如果操作不是 替换字符 而是原字符串 互换字符 位置呢

[penggeniupi]

超级赞，加上前后文，越看越通透！继续加油！

[a328223290]

回溯路径是不是直接看最小编辑距离的dp也可以，不用单独维护一个choice代表操作？

[HCWGH]

我觉得能够写出自顶向下的dp函数，就可以写出可能可以压缩的dp数组

[bianliuyang]

东哥，为什么我设置s1 = ”apple" s2= "ap"，得到的返回值是4呢，按理来说不是只需要删除三次就可以得到ap了吗

[1009058470]

扩展延申的代码

class minDistanceSolution {
    class Node {
    public:
        int val;
        int option;
        // 0 --> 什么也不做
        // 1 --> 替换
        // 2 ---> 删除
        // 3 ---> 插入
        Node() {
            val = 0;
            option = 0;
        }
        Node(int val, int option) {
            this->val = val;
            this->option = option;
        }
    };

private:
    int min3(int a, int b, int c) {
        return min(a, min(b, c));
    }
    // 把word1 向 word2靠拢
    // dp[i][j] --> word1[i..] 到 word2[j..]最小编辑距离
    int dp(string word1, int i, string word2, int j, vector<vector<minDistanceSolution::Node*>>& mono) {
        if (i == word1.size() && j == word2.size()) {
            return 0;
        }
        if (i == word1.size()) {
            // 剩下的要全部插入
            return word2.size() - j;
        }
        if (j == word2.size()) {
            // 剩下全部删除
            return word1.size() - i;
        }
        if (mono[i][j]->val != -1)
            return mono[i][j]->val;

        if (word1[i] == word2[j]) {
            mono[i][j]->val = dp(word1, i + 1, word2, j + 1, mono);
            mono[i][j]->option = 0;
            // 什么也不需要操作
            return mono[i][j]->val;
        }
        // 分别尝试 插入 删除 替换
        int insert = dp(word1, i, word2, j + 1, mono);
        int del = dp(word1, i + 1, word2, j, mono);
        int replace = dp(word1, i + 1, word2, j + 1, mono);

        int ans = min3(insert, del, replace) + 1;

        if (ans - 1 == insert) {
            mono[i][j]->option = 3;
        }
        else if (ans - 1 == del) {
            mono[i][j]->option = 2;
        }
        else {
            mono[i][j]->option = 1;
        }

        mono[i][j]->val = ans;

        return ans;
    }

    

public:
    int minDistance(string word1, string word2) {
        // 让word1 向 word2 靠近
        // 替换 2者都向后移动
        // 删除 word1 向后 word2 不动
        // 插入 word1不动 word2 动
        vector<vector<Node*>> mono(word1.size(), vector<Node*>(word2.size()));
        for (int i = 0; i < mono.size(); i++) {
            for (int j = 0; j < mono[0].size(); j++) {
                mono[i][j] = new Node(-1, -1);
            }
        }
        // 它从0，0 开始 找到word1.size()-1 , word2.size()-1
        vector<int> options;
        int i = 0, j = 0;

        int ans = dp(word1, 0, word2, 0, mono);

        // 开始推算word1怎么操作变成word2
        while (i < word1.size() && j < word2.size()) {
            options.push_back(mono[i][j]->option);
            if (mono[i][j]->option == 0 || mono[i][j]->option == 1) {
                i++; j++;
            }
            else if (mono[i][j]->option == 2) {
                i++;
            }
            else if (mono[i][j]->option == 3) {
                j++;
            }
        }

        while (i < word1.size()) {
            // 剩下全删了
            options.push_back(2);
            i++;
        }

        while (j < word2.size()) {
            options.push_back(3);
            j++;
        }

        // 此时的option 就是对word1的操作
        for (int i = 0; i < options.size(); i++) {
            cout << options[i] << " ";
        }

        return ans;
    }
};