712. 兩個字串的最小 ASCII 刪除和

思路

刪掉一些字元，讓兩個字串相等，並且刪掉的字元 ASCII 和要最小。
跟最長公共子序列一樣的方法。
定義dp[i][j]代表「s1 前 i 個字元, s2 選前 j 個字元的最佳解」。
假如現在s1[i] = s2[j]，那麼不需要刪掉任何字元，這是最好的情況。
否則s1[i] != s2[j]，兩個字元都可以刪掉。

• 刪掉s1[i]：dp[i - 1][j] + s1[i - 1]（前i個字元代表下標從0 ~ i - 1）
• 刪掉s2[j]：dp[i][j - 1] + s2[j - 1]
• 兩個一起刪掉，這個情況被前兩個包含在內。

因為每次只會用到上一行，更精確地說，當前更新格子往左上各一單位的那一格，可以將空間壓縮。

程式碼

1. 動態規劃

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
        dp[0][0] = 0;
        for(int i = 1; i <= n; ++i) {
            dp[i][0] = dp[i - 1][0] + s1[i - 1];
        }
        for(int j = 1; j <= m; ++j) {
            dp[0][j] = dp[0][j - 1] + s2[j - 1];
        }
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                if(s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
                }
            }
        }
        return dp[n][m];
    }
};

2. 動態規劃（空間壓縮1）

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        vector<int> dp(m + 1);
        dp[0] = 0;
        for(int j = 1; j <= m; ++j) {
            dp[j] = dp[j - 1] + s2[j - 1];
        }
        vector<int> lastDP = dp;
        for(int i = 1; i <= n; ++i) {
            dp[0] = lastDP[0] + s1[i - 1];
            for(int j = 1; j <= m; ++j) {
                if(s1[i - 1] == s2[j - 1]) {
                    dp[j] = lastDP[j - 1];
                }
                else {
                    dp[j] = min(lastDP[j] + s1[i - 1], dp[j - 1] + s2[j - 1]);
                }
            }
            lastDP = dp;
        }
        return dp.back();
    }
};

3. 動態規劃（空間壓縮2）

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        int prev = 0; // 左上方的數值
        vector<int> dp(m + 1);
        dp[0] = 0;
        for(int j = 1; j <= m; ++j) {
            dp[j] = dp[j - 1] + s2[j - 1];
        }
        for(int i = 1; i <= n; ++i) {
            prev = dp[0];
            dp[0] += s1[i - 1];
            for(int j = 1; j <= m; ++j) {
                int temp = dp[j];
                if(s1[i - 1] == s2[j - 1]) {
                    dp[j] = prev;
                }
                else {
                    dp[j] = min(dp[j] + s1[i - 1], dp[j - 1] + s2[j - 1]);
                }
                prev = temp;
            }
        }
        return dp.back();
    }
};

複雜度分析

• 時間複雜度：$O(nm)$
• 空間複雜度：$O(nm)$，空間壓縮$O(m)$