C ++中两个字符串的最小ASCII删除总和
假设我们有两个单词w1和w2，我们必须找到已删除字符的最低ASCII总和，以使w1和w2相同，其中在每一步中，我们可以删除任一字符串中的一个字符。因此，如果输入像“sea”和“eat”，那么输出将为231，因为我们需要从w1中删除“s”，所以它将是“ea”，并从w2中从“eat”中删除“t”。然后它们是相同的。从“进餐”中删除“t”会使总和增加116，最后，两个字符串相同，并且115+116=231是实现此目标的最小总和。
为了解决这个问题，我们将遵循以下步骤-
n：=s1的大小，m：=s2的大小
在字符串s1和s2之前添加一个空格，然后相应地更新s1和s2
制作一张大小为（n+1）x（m+1）的桌子
对于我：=1到m
dp[0，i]：=dp[0，i-1]+s2[i]
对于我：=1到n
dp[i，0]：=dp[i–1，0]+s1[i]
对于我在1到n范围内
如果s1[i]=s2[j]
否则dp[i，j]=dp[i–1，j]+1和dp[i，j-1]+1的最小值
dp[i，j]：=dp[i–1，j-1]
对于1到m范围内的j
返回dp[n，m]
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
int n = s1.size();
int m = s2.size();
s1 = " " + s1;
s2 = " " + s2;
vector < vector <int> > dp(n + 1, vector <int>(m + 1));
for(int i = 1; i <= m; i++){
dp[0][i] = dp[0][i - 1] + s2[i];
}
for(int i = 1; i <= n; i++){
dp[i][0] = dp[i - 1][0] + s1[i];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s1[i] == s2[j]){
dp[i][j] = dp[i - 1][j - 1];
}
else{
dp[i][j] = min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j]);
}
}
}
return dp[n][m];
}
};
main(){
Solution ob;
cout << (ob.minimumDeleteSum("sea", "eat"));
}输入项
"sea" "eat"
输出结果
231