न्यूनतम ASCII C++ में दो स्ट्रिंग्स के लिए योग हटाएं

मान लीजिए कि हमारे पास दो शब्द w1 और w2 हैं, हमें w1 और w2 को समान बनाने के लिए हटाए गए वर्णों का न्यूनतम ASCII योग खोजना होगा, जहां प्रत्येक चरण में हम किसी एक वर्ण को हटा सकते हैं डोरी। इसलिए यदि इनपुट "समुद्र" और "ईट" की तरह है, तो आउटपुट 231 होगा, क्योंकि हमें w1 से 's' को हटाना होगा, यह "ea" होगा और w2 से "ईट" से "t" को हटा देगा। फिर वही हैं। "ईट" से 'टी' को हटाने से योग में 116 जुड़ जाता है, और अंत में, दोनों तार समान होते हैं और इसे प्राप्त करने के लिए 115 + 116 =231 न्यूनतम योग संभव है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n :=s1 का आकार, m :=s2 का आकार
स्ट्रिंग्स s1 और s2 से पहले एक रिक्त स्थान जोड़ें, फिर s1 और s2 को तदनुसार अपडेट करें
आकार की एक तालिका बनाएं (n + 1) x (m + 1)
i के लिए :=1 से m
- dp[0, i] :=dp[0, i - 1] + s2[i]
i के लिए:=1 से n
- dp[i, 0] :=dp[i – 1, 0] + s1[i]
मैं के लिए 1 से n की सीमा में
- जे के लिए 1 से मी की सीमा में
  - अगर s1[i] =s2[j]
    - dp[i, j] :=dp[i – 1, j-1]
  - अन्य dp[i, j] =न्यूनतम dp[i – 1, j] + 1 और dp[i, j-1] + 1
रिटर्न डीपी[एन, एम]

उदाहरण(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"