這是眾所周知的Twelvefold way：
https://en.wikipedia.org/wiki/Twelvefold_way
我們想要找到以下方程的解數：
X1 X2 ... XK = target
從給定的陣列：
vector<int> vec(N);
我們可以假設 vec[i] > 0. 有 3 種情況，例如
vec = {1,2,3}, target = 5, K = 3.
Xi可以重復，解決方案可以重復。
6 個解是 {1,2,2}, {2,1,2}, {2,2,1}, {1,1,3}, {1,3,1}, {3,1,1}
Xi可以重復，解決方案不能重復。
2 個解是 {1,2,2}, {1,1,3}
Xi不能重復，解決方案不能重復。
0 解決方案。
ide 必須使用動態編程：
dp[i][k], the number of solution of target = i, K = k.
迭代關系為：
if(i > num[n-1]) dp[i][k] = dp[i-num[n-1]][k-1];
對于三種情況，它們取決于 i,n,k 的運行順序。我知道沒有 K 限制時的結果（任意數量變數的總和）：
情況1：
int KSum(vector<int>& vec, int target) {
vector<int> dp(target 1);
dp[0] = 1;
for (int i = 1; i <= target; i)
for (int n = 0; n < vec.size(); n )
if (i >= vec[n]) dp[i] = dp[i - vec[n]];
return dp.back();
}
案例2：
for (int n = 0; n < vec.size(); n )
for (int i = 1; i <= target; i)
案例3：
for (int n = 0; n < vec.size(); n )
for (int i = target; i >= 1; --i)
當有額外的變數 k 時，我們是否只需添加 for 回圈
for(int k = 1; k <= K; k )
在最外層？
編輯：
我試過case 1，只在最里面加上k的for回圈：
int KSum(vector<int> vec, int target, int K) {
vector<vector<int>> dp(K 1,vector<int>(target 1,0));
dp[0][0] = 1;
for (int n = 0; n < vec.size(); n )
for (int i = 1; i <= target; i)
for (int k = 1; k <= K; k )
{
if (i >= vec[n]) dp[k][i] = dp[k - 1][i - vec[n]];
}
return dp[K][target];
}
情況2和情況3是真的嗎？
uj5u.com熱心網友回復：
在沒有變數Kdp[i] 的解決方案中，表示有多少解決方案可以實作 sum i。
包含變數K意味著我們為子問題添加了另一個維度。此維度不一定必須位于特定軸上。您的dp陣列可能看起來像dp[i][k]或dp[k][i]。
dp[i][k]表示i使用k數字（重復或唯一）累積總和的解數dp[k][i]意味著使用k數字多少個解決方案來累積總和i
兩者都是一樣的東西。這意味著您可以在外部或內部添加回圈。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/340393.html
標籤：算法
上一篇：為K排序陣列問題編譯此代碼時出錯
下一篇：找出矩陣中水平/垂直對齊的標記