Chi phí tối thiểu để làm hai chuỗi giống nhau trong C++

Cho hai chuỗi A, B và chi phí xóa ký tự CostA, CostB. Tìm chi phí nhỏ nhất để làm A và B giống nhau bằng cách xóa ký tự. Ví dụ A="wxyz", B="wyzx", CostA=10, CostB=20 → xóa 'x' từ cả hai, chi phí = 30.

Bài toán biến thể của LCS (Longest Common Subsequence). Tìm độ dài LCS, số ký tự cần xóa = len(A) - LCS + len(B) - LCS. Chi phí = (len(A)-LCS)*CostA + (len(B)-LCS)*CostB.

Lưu ý: Code mẫu gốc có vẻ bị nhầm lẫn với bài toán khác (kiểm tra biểu diễn số trong cơ số). Dưới đây là code đúng cho bài toán chi phí làm hai chuỗi giống nhau:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int lcs(string a, string b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    return dp[n][m];
}

int minCostToMakeIdentical(string a, string b, int costA, int costB) {
    int lcsLen = lcs(a, b);
    return (a.size() - lcsLen) * costA + (b.size() - lcsLen) * costB;
}

int main() {
    string A = "wxyz", B = "wyzx";
    int costA = 10, costB = 20;
    cout << "Minimum Cost: " << minCostToMakeIdentical(A, B, costA, costB);
}

Kết quả

Minimum Cost: 30