ต้นทุนขั้นต่ำในการสร้างสตริงตัวเลขสองสตริงที่เหมือนกันใน C++

สมมติว่าเรามีสตริงตัวเลข A และ B สองสตริง เราต้องหาต้นทุนขั้นต่ำเพื่อทำให้ A และ B เหมือนกัน เราดำเนินการได้เพียงการดำเนินการเดียวเท่านั้น นั่นคือ เราสามารถลบตัวเลขออกจากสตริงได้ ค่าใช้จ่ายในการลบตัวเลขจากตัวเลขเท่ากับค่าตัวเลข สมมติว่าสตริง A =“6789”, B =“7859” จากนั้นเราต้องลบ 6 จาก A และลบ 5 จาก B ดังนั้นค่าใช้จ่ายจะเป็น 5 + 6 =11

นี่เป็นหนึ่งในรูปแบบของปัญหาลำดับต่อมาที่ยาวที่สุด เราต้องหาความยาวของ LCS จาก A และ B โดยใช้สูตรนี้ เราจะได้ต้นทุนขั้นต่ำ

ต้นทุนขั้นต่ำ=ต้นทุนA+ต้นทุนB−2∗lcs_{ต้นทุน}

ตัวอย่าง

#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