力扣712. 两个字符串的最小ASCII删除和

动态规划

• 思路：
  • 假设 dp[i][j] 是 s1 长度 i 和 s2 长度 j 两个字符串的最小 ASCII 删除和；
  • dp[i][j] 可以由：
    • 如果 s1 的第 i 个字符（s1[i - 1]）和 s2 的第 j 个字符（s2[j - 1]）不相等，则：
      • dp[i - 1][j] 加上删除 s1 的第 i 个字符，即dp[i][j] = dp[i - 1][j] + s1(i - 1);
      • dp[i][j - 1] 加上删除 s2 的第 j 个字符，即dp[i][j] = dp[i][j - 1] + s2(j - 1);
      • 取其中最小值即可；
    • 如果 s1 的第 i 个字符和 s2 的第 j 个字符相等，则：
      • dp[i][j] = dp[i - 1][j - 1]
  • 如果两个都是空串，删除和为0，即 dp[0][0] = 0
  • 如果有一个是空串，则删除和为另一个字符串所有字符的 ASCII 和：
    • dp[i][0] = dp[i - 1][0] + s1[i - 1]
    • dp[0][j] = dp[0][j - 1] + s2[j - 1]

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();

        std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
        dp[0][0] = 0;
        for (int i = 1; i < m + 1; ++i) {
            dp[i][0] = dp[i - 1][0] + s1[i - 1];
        }
        for (int j = 1; j < n + 1; ++j) {
            dp[0][j] = dp[0][j - 1] + s2[j - 1];
        }

        for (int i = 1; i < m + 1; ++i) {
            for (int j = 1; j < n + 1; ++j) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = std::min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
                }
            }
        }

        return dp[m][n];
    }
};

———————————————————————————————————————