Minimum ASCII Delete Sum for Two Strings trong C++

Cho hai chuỗi w1, w2. Tìm tổng ASCII nhỏ nhất của các ký tự cần xóa để hai chuỗi trở nên giống nhau. Mỗi bước xóa một ký tự ở một trong hai chuỗi.

Ví dụ: "sea" và "eat" → output 231. Xóa 's' (115) từ "sea" và 't' (116) từ "eat", tổng = 231.

Giải thuật (Quy hoạch động)

• n = s1.size(), m = s2.size().
• Thêm khoảng trắng đầu chuỗi để index từ 1.
• Tạo bảng dp[n+1][m+1].
• Khởi tạo hàng/cột đầu: dp[0][i] = dp[0][i-1] + s2[i], dp[i][0] = dp[i-1][0] + s1[i].
• Duyệt i=1..n, j=1..m:
  • Nếu s1[i] == s2[j]: dp[i][j] = dp[i-1][j-1].
  • Ngược lại: dp[i][j] = min(dp[i-1][j] + s1[i], dp[i][j-1] + s2[j]).
• Trả về dp[n][m].

Ví dụ code

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

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s1.size(), 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];
    }
};

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

Input

"sea" "eat"

Output

231