712. Minimum ASCII Delete Sum for Two Strings

• Time: $O(mn)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public: int minimumDeleteSum(string s1, string s2) { const int m = s1.length(); const int n = s2.length(); // dp[i][j] := min cost to make s1[0..i) and s2[0..j) equal vector> dp(m + 1, vector(n + 1)); // Delete s1[i - 1] for (int i = 1; i <= m; ++i) dp[i][0] = dp[i - 1][0] + s1[i - 1]; // Delete s2[j - 1] for (int j = 1; j <= n; ++j) dp[0][j] = dp[0][j - 1] + s2[j - 1]; 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]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public int minimumDeleteSum(String s1, String s2) { final int m = s1.length(); final int n = s2.length(); // dp[i][j] := min cost to make s1[0..i) and s2[0..j) equal int[][] dp = new int[m + 1][n + 1]; // Delete s1.charAt(i - 1) for (int i = 1; i <= m; ++i) dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1); // Delete s2.charAt(j - 1) for (int j = 1; j <= n; ++j) dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1); for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) if (s1.charAt(i - 1) == s2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1]; 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]; } }