資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究用 C++ 使兩個數字字串相同所需的最少成本
假設我們有兩個數字字串 A 和 B。我們必須找到使 A 和 B 相同的最低成本。我們只能執行一項操作，即從字串中刪除數字，從數字中刪除數字的成本與數字值相同。假設字串 A：“6789”，B：“7859”，那麼我們必須從 A 中刪除 6，從 B 中刪除 5，因此成本為 5 + 6 = 11。
這是最長公共子序列問題的變種之一。我們必須使用此公式從 A 和 B 中找到 LCS 的長度，這樣我們可以得到最低成本。
MinimumCost=CostA+CostB−2∗lcscost
示例
#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
更新日期：2019-10-21
103 次觀看
廣告