मान लीजिए हमारे पास दो संख्यात्मक स्ट्रिंग्स A और B हैं। हमें A और B को समान बनाने की न्यूनतम लागत ढूंढनी है। हम केवल एक ऑपरेशन कर सकते हैं, वह है स्ट्रिंग से अंक हटाना, एक अंक हटाने की लागत अंक के मान के समान है। मान लीजिए स्ट्रिंग A = "6789", B = "7859", तब हमें A से 6 हटाना होगा, और B से 5 हटाना होगा, तो लागत 5 + 6 = 11 होगी।
यह लॉन्गेस्ट कॉमन सबसीक्वेंस समस्या का एक प्रकार है। हमें 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
