C++-এ Minimum ASCII Delete Sum for Two Strings

এই সমস্যায় দুটি স্ট্রিং দেওয়া থাকলে, সেগুলো একই করার জন্য কতটুকু ASCII মান ডিলিট করতে হবে তার ন্যূনতম যোগফল বের করতে হবে। প্রতিটি ধাপে যেকোনো একটি স্ট্রিং থেকে একটা ক্যারেক্টার ডিলিট করা যায়।

উদাহরণ: "sea" এবং "eat" -> আউটপুট 231। 's' (115) এবং 't' (116) ডিলিট করতে হবে। যোগফল = 231।

সমাধানের পদ্ধতি (Dynamic Programming - LCS Variant)

dp[i][j] = s1[0..i-1] এবং s2[0..j-1] একই করার জন্য ন্যূনতম ASCII ডিলিট সাম।
বেস কেস: dp[0][j] = dp[0][j-1] + ASCII(s2[j-1]), dp[i][0] = dp[i-1][0] + ASCII(s1[i-1])।
ট্রানজিশন:
- যদি s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]।
- অন্যথায়: dp[i][j] = min(dp[i-1][j] + ASCII(s1[i-1]), dp[i][j-1] + ASCII(s2[j-1]))।

উদাহরণ (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++) dp[i][0] = dp[i-1][0] + s1[i-1];
        for (int j = 1; j <= m; j++) dp[0][j] = dp[0][j-1] + s2[j-1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1]);
            }
        }
        return dp[n][m];
    }
};

int main() {
    Solution ob;
    cout << ob.minimumDeleteSum("sea", "eat");
    return 0;
}

ইনপুট

"sea" "eat"