Leetcode上有一个系列的问题
- 在一个数组中找寻2个数的和值为target
- 在一个数组中找寻3个数的和值为target
- 在一个数组中找寻4个数的和值为target
在一个给定的数组A中找寻k个数，使其值等于target，一共有多少种方案。
这道题用DP来做。
result[i][j][target]
i表示数组的大小。j 标识找寻多少个值。k标识目标值。A表示给定数组。
所有有
result[i][j][target] = result[i - 1][j - 1][target - A[i]] + result[i - 1][j][target];
站在i的位置考虑，即考虑是否需要i位的值。
result[i - 1][j][target] 表示不需要i位的值
result[i - 1][j - 1][target - A[i]] 表示需要i位的值
public int kSum(int[] A, int k, int target) {
int result[][][] = new int[A.length + 1][k + 1][target + 1];
for (int i = 0; i < A.length + 1; i++) {
result[i][0][0] = 1;
}
for (int h = 1; h < A.length + 1 ; h++) {
int min = Math.min(h, k);
for (int i = 1; i <= min; i++) {
for (int j = 1; j <= target; j++) {
if(j >= A[h - 1]) {
result[h][i][j] = result[h - 1][i][j] + result[h - 1][i - 1][j - A[h- 1]];
}else {
result[h][i][j] = result[h - 1][i][j];
}
}
}
}
printNums(result[A.length], k + 1, target +1);
return result[A.length ][k][target];
}
另外有一种比较简便的方法：
参考 https://www.jianshu.com/p/e5a6d7c356e6
不过我看不太懂怎么从3维简化成了一位。以及倒序便利。。。惭愧……
