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

Cho hai chuỗi số A, B. Chi phí xóa một chữ số bằng giá trị của chữ số đó. Tìm chi phí nhỏ nhất để làm A, B giống nhau. Ví dụ A="6789", B="7859" → xóa '6' từ A (chi phí 6), xóa '5' từ B (chi phí 5), tổng = 11.

Biến thể LCS có trọng số: LCS tối đa hóa tổng giá trị chữ số chung. Công thức: MinCost = Cost(A) + Cost(B) - 2 * LCS_cost.

Ví dụ

#include <iostream>
using namespace std;

int longest_common_subsequence(int dp[101][101], string a, string b, int a_len, int b_len) {
    for (int i = 0; i < 101; i++)
        for (int j = 0; j < 101; j++)
            dp[i][j] = -1;
    if (a_len < 0 || b_len < 0)
        return 0;
    if (dp[a_len][b_len] != -1)
        return dp[a_len][b_len];
    int res = 0;
    if (a[a_len] == b[b_len]) {
        res = int(a[a_len] - '0') + longest_common_subsequence(dp, a, b, a_len - 1, b_len - 1);
    } else
        res = max(longest_common_subsequence(dp, a, b, a_len - 1, b_len),
                  longest_common_subsequence(dp, a, b, a_len, b_len - 1));
    dp[a_len][b_len] = res;
    return res;
}

int minCost(string str) {
    int cost = 0;
    for (int i = 0; i < str.length(); i++)
        cost += int(str[i] - '0');
    return cost;
}

int main() {
    string a = "6789", b = "7859";
    int dp[101][101];
    cout << "Minimum Cost to make these two numbers identical: "
         << (minCost(a) + minCost(b) - 2 * longest_common_subsequence(dp, a, b, a.length() - 1, b.length() - 1));
    return 0;
}

Kết quả

Minimum Cost to make these two numbers identical: 11