本文共 2093 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要找到两个字符串s1和s2，使得经过删除一些字符后，它们相等，并且使得删除的字符的ASCII值之和最小。

方法思路

这个问题可以通过动态规划来解决。我们定义一个二维数组dp，其中dp[i][j]表示处理到s1的前i个字符和s2的前j个字符时，最小的删除和。状态转移方程如下：

通过这种方法，我们可以逐步填充dp表，找到最小的删除和。

解决代码

public class Solution {    public int minimumDeleteSum(String s1, String s2) {        int n1 = s1.length();        int n2 = s2.length();        int[][] dp = new int[n1 + 1][n2 + 1];        for (int i = 0; i <= n1; i++) {            for (int j = 0; j <= n2; j++) {                dp[i][j] = Integer.MAX_VALUE;            }        }        dp[0][0] = 0;        for (int i = 0; i <= n1; i++) {            dp[i + 1][0] = dp[i][0] + (i > 0 ? s1.charAt(i - 1) : 0);        }        for (int j = 0; j <= n2; j++) {            dp[0][j + 1] = dp[0][j] + (j > 0 ? s2.charAt(j - 1) : 0);        }        for (int i = 0; i <= n1; i++) {            for (int j = 0; j <= n2; j++) {                if (i == 0 && j == 0) continue;                char c1 = s1.charAt(i - 1);                char c2 = s2.charAt(j - 1);                if (c1 == c2) {                    if (dp[i][j] < dp[i + 1][j + 1]) {                        dp[i + 1][j + 1] = dp[i][j];                    }                    if (dp[i][j] + c1 < dp[i + 1][j]) {                        dp[i + 1][j] = dp[i][j] + c1;                    }                    if (dp[i][j] + c2 < dp[i][j + 1]) {                        dp[i][j + 1] = dp[i][j] + c2;                    }                } else {                    if (dp[i][j] + c1 < dp[i + 1][j]) {                        dp[i + 1][j] = dp[i][j] + c1;                    }                    if (dp[i][j] + c2 < dp[i][j + 1]) {                        dp[i][j + 1] = dp[i][j] + c2;                    }                }            }        }        return dp[n1][n2];    }}

代码解释

转载地址：http://rulc.baihongyu.com/