经典动态规划：最长公共子序列 :: labuladong的算法小抄

[labuladong]

文章链接点这里：经典动态规划：最长公共子序列

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

[SaulZhang]

712. 两个字符串的最小ASCII删除和（中等） python版本解法

class Solution:
    '''
    问题等价: 求最长公共子序列的最大ASCII码值的和，
    '''
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        dp = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]
        for i in range(1,len(s1)+1):
            for j in range(1,len(s2)+1):
                if s1[i-1] == s2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+ord(s1[i-1])
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        ascSum = 0
        ascSum += sum([ord(char) for char in list(s1)])
        ascSum += sum([ord(char) for char in list(s2)])
        return ascSum - 2*dp[len(s1)][len(s2)]

[kuangkuangkuangha]

1143.C++

class Solution {
public:
    // 定义dp返回 text1从i， text2从j开始的公共子序列的长度
    int dp(string text1, int i, string text2, int j, vector<vector<int>>& memo)
    {
        if(i==text1.length() || j==text2.length())
            return 0;

        if(memo[i][j] != -1)
            return memo[i][j];

        if(text1[i]==text2[j])
            memo[i][j] = 1 + dp(text1, i+1, text2, j+1, memo);
        else
        {
            memo[i][j] = max(dp(text1, i+1, text2, j, memo),
            dp(text1, i, text2, j+1, memo));
        }

        return memo[i][j];
    }

    int longestCommonSubsequence(string text1, string text2) {
        // 定义备忘录
        vector< vector<int> > memo(text1.size(), vector<int>(text2.size(), -1));
        return dp(text1, 0, text2, 0, memo);
    }
};

力扣自顶而下居然超时， 定义了备忘录也会的吗呜呜呜～

[labuladong]

@kuangkuangkuangha 是你代码写得有问题吧，递归函数的参数怎么能传值呢？string 改成 string& 试试。

[kuangkuangkuangha]

@labuladong 雀氏哦，稳啊！传参数会拷贝的，内存大，耗时，牛蛙，谢谢啦！

[1302304703]

712 两个字符串最小ASCII删除和 自底向上dp解法

public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        //s1[...i]和s2[...j]若要成为相等的字符串所需要删除的字符的ASCII值的最小和为dp[i][j]
        int[][] dp = new int[m + 1][n + 1];
        //base case
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1),
                            dp[i][j - 1] + s2.charAt(j - 1));
                }
            }
        }
        return dp[m][n];
    }

[bert82503]

打卡，感谢楼主！

[LebronHarden1]

请问怎么一上来就知道这题用dp的

[oliyg]

582 题的 js 解法，习惯用空白字符给两个字符串增加前缀，避免偏移量

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    // 避免偏移量
    word1 = " " + word1;
    word2 = " " + word2;
    const rows = word1.length;
    const cols = word2.length;
    // dp[i][j] 含义：到 i,j 位置时，使得字符串相同的最小步骤
    const dp = new Array(rows)
        .fill(0)
        .map(() => new Array(cols).fill(Number.MAX_SAFE_INTEGER));
    // init
    dp[0][0] = 0; // 第一个字符相等，不需要操作
    for (let row = 1; row < rows; row++) {
        dp[row][0] = row;
    }
    for (let col = 1; col < cols; col++) {
        dp[0][col] = col;
    }
    // tra
    for (let row = 1; row < rows; row++) {
        for (let col = 1; col < cols; col++) {
            if (word1[row] === word2[col]) {
                // 相等，不需要删除
                dp[row][col] = dp[row - 1][col - 1];
            } else {
                const ifDeleteRow = dp[row][col - 1] + 1; // word2 不需要动
                const ifDeleteCol = dp[row - 1][col] + 1; // word1 不需要动
                dp[row][col] = Math.min(ifDeleteRow, ifDeleteCol);
            }
        }
    }
    return dp[rows - 1][cols - 1];
};

[deepbreath373]

LC.712 - DP 数组自底向上

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i <= m; i++){
            dp[i][0] = s1.charAt(i-1) + dp[i-1][0];
        }
        for(int j = 1; j <= n; j++){
            dp[0][j] = s2.charAt(j-1) + dp[0][j-1];
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j]+s1.charAt(i-1), dp[i][j-1]+s2.charAt(j-1));
                }
            }
        }
        return dp[m][n];
    }
}

[MzxlM]

内存压缩版

class Solution {
    // int[][] dp;
    int[] dp;
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        // dp = new int[m+1][n+1];
        dp = new int[n+1];
        
        for(int i = 1; i <= m; i++) {
            int pre = 0;
            for(int j = 1; j <=n; j++) {
                int temp = dp[j];
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    // dp[i][j] = 1+ dp[i - 1][j - 1];
                    dp[j] = 1+pre;
                }else {
                    // dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                    dp[j] = Math.max(dp[j-1],dp[j]);
                }
                pre = temp;
            }
                
        }
        return dp[n];
    }
}

[Ruoyi-Chen]

东哥，向您请教一个问题：

712. 两个字符串的最小ASCII删除和

从后往前对比两个字符串的，加上memo之后就不对了，如果东哥看到可以帮我看看哪里出问题了吗 非常感谢！！

class Solution {
    int[][] memo;
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        memo = new int[m][n];
        for(int[] mm : memo) Arrays.fill(mm, -1);
        
        return dp(s1, m - 1, s2, n - 1, 0);
    }

    public int dp(String s1, int i, String s2, int j, int sum) {
        // base case
        if(i < 0) {
            for(int k = j; k >= 0; k--){
                sum += s2.charAt(k);
            }
            return sum;
        }
        if(j < 0) {
            for(int k = i; k >= 0; k--) {
                sum += s1.charAt(k);
            }
            return sum;
        }

        // 把从memo找的这步注掉就没问题，加上答案就不对
        if(memo[i][j] != -1) return memo[i][j];

        //dp
        if(s1.charAt(i) == s2.charAt(j)) {
            memo[i][j] = dp(s1, i - 1, s2, j - 1, sum);
        } else {
            memo[i][j] = Math.min(dp(s1, i, s2, j - 1, sum + s2.charAt(j)), 
                            dp(s1, i - 1, s2, j, sum + s1.charAt(i)));
        }

        return memo[i][j];
    }
}