Leetcode|线性序列|712. 两个字符串的最小ASCII删除和（变相LCS）

SL_World

发布于 2021-09-18 16:44:36

5860

文章被收录于专栏：XX

1 动态规划（变相最长公共子序列）

【本题特点】：dp数组不仅能存储子序列的长度，还能存储子序列本身，确实可以很灵活

dp[i][j] = dp[i - 1][j - 1] + s1[i - 1];
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int asize = s1.size();
        int bsize = s2.size();
        vector<vector<int>> dp(asize + 1, vector<int>(bsize + 1, 0));
        for (int i = 1; i <= asize; i++)
            for (int j = 1; j <= bsize; j++) {
                if (s1[i - 1] == s2[j - 1]) 
                    dp[i][j] = dp[i - 1][j - 1] + s1[i - 1];
                else 
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        return accumulate(s1.begin(),s1.end(),0) + accumulate(s2.begin(),s2.end(),0) - 2*dp[asize][bsize];
    }
};