https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/description/
All elements of each string will have an ASCII value in
X.
http://www.cnblogs.com/grandyang/p/7752002.html
Given two strings
s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.
Example 1:
Input: s1 = "sea", s2 = "eat" Output: 231 Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum. Deleting "t" from "eat" adds 116 to the sum. At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.
Example 2:
Input: s1 = "delete", s2 = "leet" Output: 403 Explanation: Deleting "dee" from "delete" to turn the string into "let", adds 100[d]+101[e]+101[e] to the sum. Deleting "e" from "leet" adds 101[e] to the sum. At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403. If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.
Note:
0 < s1.length, s2.length <= 1000.[97, 122].http://www.cnblogs.com/grandyang/p/7752002.html
下面这种方法思路也很巧妙，反其道而行之，相当于先计算了字符串s1和s2的最大相同子序列，在这道题中就是最大相同子序列的ASCII码值，然后用s1和s2的所有字符之和减去这个最大ASCII码值的两倍，就是要删除的字符的最小ASCII码值了。那么还是建立二维数组dp，其中dp[i][j]表示字符串s1的前i个字符和字符串s2点前j个字符中的最大相同子序列的ASCII值。然后我们遍历所有的位置，当对应位置的字符相等时，s1[i-1] == s2[j-1]，那么我们直接赋值为上一个状态的dp值加上这个相同的字符，即dp[i-1][j-1] + s1[i-1]，注意这里跟解法一不同之处，因为dp的定义不同，所以写法不同。如果s1[i-1] != s2[j-1]，那么就有两种情况，我们可以删除s[i-1]的字符，即dp[i-1][j]，或者删除s[j-1]的字符，即dp[i][j-1]，取二者中最大值赋给dp[i][j]。最后分别算出s1和s2的累加值，减去两倍的dp最大值即可
int minimumDeleteSum(string s1, string s2) { int m = s1.size(), n = s2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); 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] + s1[i - 1]; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } int sum1 = accumulate(s1.begin(), s1.end(), 0); int sum2 = accumulate(s2.begin(), s2.end(), 0); return sum1 + sum2 - 2 * dp[m][n]; }
Let
dp[i][j] be the answer to the problem for the strings s1[i:], s2[j:].
When one of the input strings is empty, the answer is the ASCII-sum of the other string. We can calculate this cumulatively using code like
dp[i][s2.length()] = dp[i+1][s2.length()] + s1.codePointAt(i).
When
s1[i] == s2[j], we have dp[i][j] = dp[i+1][j+1] as we can ignore these two characters.
When
s1[i] != s2[j], we will have to delete at least one of them. We'll have dp[i][j] as the minimum of the answers after both deletion options.
The solutions presented will use bottom-up dynamic programming.
public int minimumDeleteSum(String s1, String s2) { int[][] dp = new int[s1.length() + 1][s2.length() + 1]; for (int i = s1.length() - 1; i >= 0; i--) { dp[i][s2.length()] = dp[i+1][s2.length()] + s1.codePointAt(i); } for (int j = s2.length() - 1; j >= 0; j--) { dp[s1.length()][j] = dp[s1.length()][j+1] + s2.codePointAt(j); } for (int i = s1.length() - 1; i >= 0; i--) { for (int j = s2.length() - 1; j >= 0; j--) { if (s1.charAt(i) == s2.charAt(j)) { dp[i][j] = dp[i+1][j+1]; } else { dp[i][j] = Math.min(dp[i+1][j] + s1.codePointAt(i), dp[i][j+1] + s2.codePointAt(j)); } } } return dp[0][0]; }
public int minimumDeleteSum(String s1, String s2) {
// dp(n,m) the cost if a[n]==b[m] dp(n-1, m-1)
// __________if != min{dp(n-1, m)+cost(a[n]), dp(n,m-1)+cost(b[m]), .... }
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
dp[0][1] = s2.charAt(0);
dp[1][0] = s1.charAt(0);
for (int i = 0; i < s1.length(); i++) {
int dpi = i + 1;
dp[dpi][0] = dp[dpi - 1][0] + s1.charAt(i);
}
for (int j = 0; j < s2.length(); j++) {
int dpj = j + 1;
dp[0][dpj] = dp[0][dpj - 1] + s2.charAt(j);
}
for (int i = 0; i < s1.length(); i++) {
for (int j = 0; j < s2.length(); j++) {
int dpi = i + 1, dpj = j + 1;
dp[dpi][dpj] = Integer.MAX_VALUE;
// delete i from s1
dp[dpi][dpj] = Math.min(dp[dpi][dpj], dp[dpi - 1][dpj] + s1.charAt(i));
// delete j from s2
dp[dpi][dpj] = Math.min(dp[dpi][dpj], dp[dpi][dpj - 1] + s2.charAt(j));
if (s1.charAt(i) == s2.charAt(j)) {
dp[dpi][dpj] = Math.min(dp[dpi][dpj], dp[dpi - 1][dpj - 1]);
}
// delete both
else {
dp[dpi][dpj] = Math.min(dp[dpi][dpj], dp[dpi - 1][dpj - 1] + s1.charAt(i) + s2.charAt(j));
}
}
}
return dp[s1.length()][s2.length()];
}
