题目

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/

题解

经典的 暴力递归 -> 傻缓存 -> DP

实际上是找两个字符串的 最大ASCII码和 的公共子序列，然后用总的 ASCII 之和减一下就行了。可以参考两个字符串的最长公共子序列，只不过取 max 的依据不同，一个是 ASCII 码相加，一个是取长度。

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int sum = 0;
        for (int i = 0; i < s1.length(); i++) {
            sum += s1.charAt(i);
        }
        for (int i = 0; i < s2.length(); i++) {
            sum += s2.charAt(i);
        }

        // Approach 1: Recursive, Brute Force
// return sum - process1(s1, s2, 0, 0);

        // Approach 2: Recursion with Memoization
// int[][] dp = new int[s1.length() + 1][s2.length() + 1];
// for (int i = 0; i < dp.length - 1; i++) {
// for (int j = 0; j < dp[0].length - 1; j++) {
// dp[i][j] = -1;
// }
// }
// return sum - process2(s1, s2, 0, 0, dp);

        // Approach 3: Dynamic Programming
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = s1.length() - 1; i >= 0; i--) {
            for (int j = s2.length() - 1; j >= 0; j--) {
                int p1 = s1.charAt(i) == s2.charAt(j) ? dp[i + 1][j + 1] + s1.charAt(i) + s2.charAt(j) : 0;
                int p2 = dp[i + 1][j];
                int p3 = dp[i][j + 1];
                dp[i][j] = Math.max(p1, Math.max(p2, p3));
            }
        }
        return sum - dp[0][0];

    }

// public int process2(String s1, String s2, int i, int j, int[][] dp) {
// if (dp[i][j] >= 0) return dp[i][j];
// int p1 = s1.charAt(i) == s2.charAt(j) ? process2(s1, s2, i + 1, j + 1, dp) + s1.charAt(i) + s2.charAt(j) : 0;
// int p2 = process2(s1, s2, i + 1, j, dp);
// int p3 = process2(s1, s2, i, j + 1, dp);
// dp[i][j] = Math.max(p1, Math.max(p2, p3));
// return dp[i][j];
// }

// public int process1(String s1, String s2, int i, int j) {
// if (i == s1.length() || j == s2.length()) return 0;
// int p1 = s1.charAt(i) == s2.charAt(j) ? process1(s1, s2, i + 1, j + 1) + s1.charAt(i) + s2.charAt(j) : 0;
// int p2 = process1(s1, s2, i + 1, j);
// int p3 = process1(s1, s2, i, j + 1);
// return Math.max(p1, Math.max(p2, p3));
// }
}