# 712 - Minimum ASCII Delete Sum for Two Strings

解法一 - DP

我們可以先算出 s1 跟 s2 的 longest common subsequence，然後把 s1 & s2 中不屬於 longest common subsequence 的字母都刪掉，就可以算出答案。

以下是程式碼：

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        // Get longets common subsequence (LCS)
        vector<vector<int>> dp(s1.length()+1, vector<int>(s2.length()+1, 0));

        int maxLen = 0, x, y;
        for(int i=1; i<=s1.length(); i++) {
            for(int j=1; j<=s2.length(); j++) {
                if(s1[i-1] == s2[j-1]) {
                    dp[i][j] = 1+dp[i-1][j-1];
                }
                else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }

                if(dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    x = i;
                    y = j;
                }
            }
        }

        string LCS;
        while(dp[x][y] > 0) {
            if(dp[x][y] > max(dp[x-1][y], dp[x][y-1])) {
                LCS += s1[x-1];
                x--;
                y--;
            }
            else if(dp[x][y] == dp[x-1][y]) {
                x--;
            }
            else
                y--;
        }
        reverse(LCS.begin(), LCS.end());

        cout << LCS << endl;
        cout << (int)('t'-'j') << endl;

        // Calculate the sum of all chars not in LCS
        int minSum = 0;

        int ptr = 0;
        for(int i=0; i<s1.length(); i++) {
            if(s1[i] != LCS[ptr])
                minSum += (int)s1[i];
            else
                ptr++;
        }

        ptr = 0;
        for(int i=0; i<s2.length(); i++) {
            if(s2[i] != LCS[ptr])
                minSum += (int)s2[i];
            else
                ptr++;
        }

        return minSum;
    }
};

不過這個解法會在一些情況下出錯，比如說：

"vwojt"
"saqhgdrarwntji"

因為 "wj" 跟 "wt" 都算是 LCS，但我算出的 LCS 是 "wj"，所以我會把 s1 跟 s2 的 t 都刪掉而不是刪掉 j，所以會多花 2*('t'-'j') == 20 的成本。

不過我覺得這個解法很有教育意義，所以還是記錄一下：

解法二 - DP

這篇討論寫得很清楚，直接把 cost 是多少存在 dp table 中：

dp[i][j] is the cost for s1.substr(0,i) and s2.substr(0, j). 
Note s1[i], s2[j] not included in the substring.

Base case: dp[0][0] = 0
target: dp[m][n]

if s1[i-1] = s2[j-1]   // no deletion
    dp[i][j] = dp[i-1][j-1];
else   // delete either s1[i-1] or s2[j-1]
    dp[i][j] = min(dp[i-1][j]+s1[i-1], dp[i][j-1]+s2[j-1]);

初始化的地方就是 s1 = "" 或 s2 = ""，那每一個 char 都是要刪掉 cost。實作如下：

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        // Init
        for (int i = 1; i <= m; i++) 
            dp[i][0] = dp[i-1][0]+s1[i-1];

        for (int j = 1; j <= n; j++)
            dp[0][j] = dp[0][j-1]+s2[j-1]; 

        // Build dp table 
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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[m][n];
    }
};