ধরুন আমাদের দুটি সংখ্যাসূচক স্ট্রিং A এবং B আছে। A এবং Bকে অভিন্ন করার জন্য আমাদের সর্বনিম্ন খরচ খুঁজে বের করতে হবে। আমরা শুধুমাত্র একটি অপারেশন করতে পারি, তা হল আমরা স্ট্রিং থেকে অঙ্কগুলি মুছে ফেলতে পারি, সংখ্যা থেকে একটি সংখ্যা মুছে ফেলার জন্য মূল্য অঙ্কের মানের সমান। ধরুন A =“6789”, B =“7859” স্ট্রিং, তারপর আমাদের A থেকে 6 মুছে ফেলতে হবে এবং B থেকে 5 মুছে ফেলতে হবে, তাহলে খরচ হবে 5 + 6 =11।
এটি Longest Common Subsequence সমস্যার একটি পরিবর্তন। আমাদের A এবং B থেকে LCS এর দৈর্ঘ্য খুঁজে বের করতে হবে, এই সূত্রটি ব্যবহার করে, আমরা সর্বনিম্ন খরচ পেতে পারি।
MinimumCost=CostA+CostB−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
