給定 n 個不同的正整數，整數 k（k <= n）以及一個目標數字 target，
在這 n 個數里面找出 k 個數，使得這 k 個數的和等于目標數字，求問有多少種方案？
在線評測地址：LintCode 領扣
樣例1
輸入:
List = [1,2,3,4]
k = 2
target = 5
輸出: 2
說明: 1 + 4 = 2 + 3 = 5 樣例2
輸入:
List = [1,2,3,4,5]
k = 3
target = 6
輸出: 1
說明: 只有這一種方案， 1 + 2 + 3 = 6 演算法：dp
如果沒有k的約束，我們可以發現，這題就可以轉化為背包問題，利用n個正整數達到目標target，那么有了k的約束之后，我們需要用額外的一維來維護使用的數字，所以約定狀態如下，用dp[i][j][k]表示前ii個數里選j個和為k的方案數，
- 假定dp[i][j][k]之前的方案數都已知，考慮dp[i][j][k]的情況，
- dp[i][j][k]可以由dp[i?1][j?1][k?A[i?1]]的狀態取?A[i-1]?得到，
- dp[i][j][k]也可以由dp[i?1][j][k]直接得到，即不取?A[i-1]?，
- 最后回傳f[n][k][target]即可，
復雜度分析
- 時間復雜度O(n?k?target)O(n?k?target)
- 空間復雜度O(n?k?target)O(n?k?target)
- 時間復雜度與空間復雜度是等價的，
- 在這里，空間復雜度可以用滾動陣列優化，
public class Solution {
/**
* @param A: an integer array.
* @param k: a positive integer (k <= length(A))
* @param target: a integer
* @return an integer
*/
public int kSum(int A[], int k, int target) {
int n = A.length;
int[][][] f = new int[n + 1][k + 1][target + 1];
for (int i = 0; i < n + 1; i++) {
f[i][0][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k && j <= i; j++) {
for (int t = 1; t <= target; t++) {
f[i][j][t] = 0;
if (t >= A[i - 1]) {
f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
}
f[i][j][t] += f[i - 1][j][t];
} // for t
} // for j
} // for i
return f[n][k][target];
}
} 更多題解參考：九章演算法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/218811.html
標籤：其他