Minimum Cost ทำให้ Numeric Strings เหมือนกันใน C++

สมมติมี Numeric Strings A และ B ต้องการ Minimum Cost ทำให้เหมือนกัน Operation เดียวคือลบ Digits Cost ลบ Digit = ค่าของ Digit ตัวอย่าง A="6789", B="7859" ลบ 6 จาก A และ 5 จาก B Cost = 5+6=11

Variation ของ LCS หา LCS Cost แล้วใช้สูตร: MinimumCost = CostA + CostB - 2*lcs_cost

ตัวอย่างโค้ด C++

#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 < 100; i++)
        for (int j = 0; j < 100; 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] - 48) + 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] - 48);
    return cost;
}

int main() {
    string a, b;
    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;
}

ผลลัพธ์

Minimum Cost to make these two numbers identical: 11