# 712 - Minimum ASCII Delete Sum for Two Strings

## 解法一 - DP

``````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"
``````

## 解法二 - DP

``````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]);
``````

``````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];
}
};
``````