经典动态规划：最长公共子序列 :: 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];
    }
}

[yonggui-yan]

打卡打卡

[GXhunter]

这种题还是用备忘录好理解一点，和编辑距离有点像

class Solution {
    Integer[][] memo;
    int m;
    int n;
    public int longestCommonSubsequence(String text1, String text2) {
        m = text1.length();
        n = text2.length();
        memo = new Integer[m][n];
        return dp(text1, 0, text2, 0);
    }

    /**
     * text1[i:] 与 text2[j:] 的lcs
     */
    private int dp(String text1, int i, String text2, int j) {
        if (i == m || j == n) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        if (text1.charAt(i) == text2.charAt(j)) {
            return memo[i][j] = 1 + dp(text1, i + 1, text2, j + 1);
        }
        return memo[i][j] = max(dp(text1, i + 1, text2, j), dp(text1, i, text2, j + 1));
    }

    private int max(int... nums) {
        int max = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
        }
        return max;
    }
}

[BinaryOracle]

class Solution {
    private int[][] memo;
    public int minDistance(String word1, String word2) {
        memo=new int[word1.length()][word2.length()];
        for(int[] m:memo){
            Arrays.fill(m,-1);
        }
        return dp(word1,0,word2,0);
    }

    public int dp(String s1,int i,String s2,int j){
         if(i==s1.length()){
             return s2.length()-j;
         }
         if(j==s2.length()){
             return s1.length()-i;
         }
         if(memo[i][j]!=-1){
             return memo[i][j];
         }
         //相等无需删除,直接跳过
         if(s1.charAt(i)==s2.charAt(j)){
             memo[i][j]=dp(s1,i+1,s2,j+1);
         }else{
             //不相等进行删除
             memo[i][j]=Math.min(
                dp(s1,i+1,s2,j),
                dp(s1,i,s2,j+1) 
             )+1;
         }
         return memo[i][j];
    }
}

[CarlLy7]

打卡，慢慢开始摸到门道