Chi phí tối thiểu để tạo hai chuỗi số giống hệt nhau trong C ++

Giả sử chúng ta có hai chuỗi số A và B. Chúng ta phải tìm chi phí tối thiểu để làm cho A và B giống hệt nhau. Chúng tôi chỉ có thể thực hiện một thao tác, đó là chúng tôi có thể xóa các chữ số khỏi chuỗi, chi phí cho việc xóa một chữ số khỏi số bằng với giá trị của chữ số. Giả sử chuỗi A =“6789”, B =“7859”, sau đó chúng ta phải xóa 6 khỏi A và xóa 5 khỏi B, vì vậy chi phí sẽ là 5 + 6 =11.

Đây là một trong những biến thể của bài toán Thứ tự chung dài nhất. Chúng ta phải tìm độ dài của LCS từ A và B, bằng cách sử dụng công thức này, chúng ta có thể nhận được chi phí tối thiểu.

MinimumCost =CostA + CostB − 2 ∗ lcs _{chi phí}

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 < 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;
}

Đầu ra

Minimum Cost to make these two numbers identical: 11