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

本文主要是介绍力扣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];}
};

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