ধরুন আমাদের দুটি নümerিক স্ট্রিং A এবং B আছে। আমাদের A এবং B কে অভিন্ন করার ন্যূনতম খরচ বের করতে হবে। আমরা শুধু একটি অপারেশন পারফর্ম করতে পারি: স্ট্রিং থেকে ডিজিট ডিলিট করা, ডিজিট ডিলিট করার খরচ সেটি ডিজিটের মান সমান। ধরুন A = "6789", B = "7859", তবে A থেকে ৬ এবং B থেকে ৫ ডিলিট করতে হবে, তাই খরচ ৫ + ৬ = ১১।
এটি LCS সমস্যার একটি ভ্যারিয়েশন। আমাদের A এবং B থেকে LCS বের করতে হবে, এবং নিচের ফর্মুলা ব্যবহার করে ন্যূনতম খরচ বের করা যাবে:
MinimumCost = CostA + CostB - 2 * lcs_cost
উদাহরণ
#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
