# Concise DP solution

• The same idea as edit distance. Straightforward 19 lines.

``````class Solution {
public int minimumDeleteSum(String s1, String s2) {
int[][] count = new int[s1.length() + 1][s2.length() + 1];
for(int i = 1; i < count.length; i++){
count[i][0] = count[i-1][0] + s1.charAt(i-1);
}
for(int i = 1; i < count[0].length; i++){
count[0][i] = count[0][i-1] + s2.charAt(i-1);
}
for(int i = 1; i < count.length; i++){
for(int j = 1; j < count[0].length; j++){
int cost = (s1.charAt(i-1) == s2.charAt(j-1))? 0 : s1.charAt(i-1) + s2.charAt(j-1);
count[i][j] = Math.min(count[i-1][j] + s1.charAt(i-1), count[i][j-1] + s2.charAt(j-1));
count[i][j] = Math.min(count[i][j], count[i-1][j-1] + cost);
}
}
return count[s1.length()][s2.length()];
}
}
````````

• @DonaldTrump Dear President, I rewrote your solution in C++, even shorter.

``````   int minimumDeleteSum(string s1, string s2) {
int m = s1.size(), n = s2.size();
int dp[m+1][n+1] = {0};
for (int j = 1; j <= n; j++) dp[0][j] = dp[0][j-1]+s2[j-1];
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[i][j] = s1[i-1] == s2[j-1]? dp[i-1][j-1]:min(dp[i-1][j]+s1[i-1], dp[i][j-1]+s2[j-1]);
}
return dp[m][n];
}
``````

• In case you didn't realize, your solution can be optimized by using a 1D array, either dp[string1.length()] or dp[string2.length()]

• @zestypanda plz change ur name to Kim Joungeun Lol
You are genius!

• another Java 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 i - 1 and j - 1 are the same, use the previous result
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}
// else compare the sums of previous results and current
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];

}``````

• Similarly edit distance algorithm bottom-up, 13 line

``````class Solution {
public int minimumDeleteSum(String s1, String s2) {
int[][] dp = new int[s1.length () + 1][s2.length () + 1];
for (int i = 0; i < s1.length () + 1; i++)
for (int j = 0; j < s2.length () + 1; j++)
if (i == 0 && j == 0) dp[i][j] = 0;
else if (i == 0) dp[i][j] = s2.charAt (j - 1) + dp[i][j - 1];
else if (j == 0) dp[i][j] = s1.charAt (i - 1) + dp[i - 1][j];
else if (s1.charAt (i - 1) == s2.charAt (j - 1)) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = Math.min (s1.charAt (i - 1) + dp[i - 1][j], s2.charAt (j - 1) + dp[i][j - 1]);
return dp[s1.length ()][s2.length ()];
}
}
``````

Although I would recommend converting `toCharArray` first.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.