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