[LintCode] k Sum [三维动态规划]
文章目录
Problem
Given n distinct positive integers, integer k (k <= n) and a number target.
Find k numbers where sum is target. Calculate how many solutions there are?
Example
Given [1,2,3,4], k = 2, target = 5.
There are 2 solutions: [1,4] and [2,3].
Return 2.
Note
这道题和Distinct Subsequence很像。
使用三维动规数组dp[i][j][t],表示从0遍历到A[i]后找到的j个元素之和为t的情况的总数。最后返回从整个A数组找到的k个元素之和为target的情况总数即可。操作如下:
首先,若第i个元素,也就是A[i-1],大于t,那么“从前i个元素中取j个元素令j个元素之和为t的所有情况”和第i个元素无关。也就是说dp[i][j][t] = dp[i-1][j][t]。而如果最后一个元素A[i-1] <= t,那么这个元素一定能带来一些不同的“从前i个元素中取j个元素令j个元素之和为t的情况”,但是,还要加上完全不考虑这个元素A[i-1]时的解的集合,也就是dp[i-1][j-1][t-A[i-1]]。因为,加上这个元素之后的dp[i][j-1][t-A[i-1]]不会影响已经遍历过的dp[i-1][j-1][t-A[i-1]]。
Solution
public class Solution {
public int kSum(int A[], int k, int target) {
int[][][] dp = new int[A.length+1][k+1][target+1];
for (int i = 0; i <= A.length; i++) dp[i][0][0] = 1;
//Super DP
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= k && j <= i; j++) {
for (int t = 1; t <= target; t++) {
dp[i][j][t] = dp[i-1][j][t];
if (A[i-1] <= t) dp[i][j][t] += dp[i-1][j-1][t-A[i-1]];
}
}
}
return dp[A.length][k][target];
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论