d****n
发帖数: 233 | 1 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.
我用递归如下：
void helper(vector A,int k, int start,int target, int & ans) {
if (k < 0 || target < 0) return;
if (k == 0 && target == 0) {
ans++;
return;
}
for(int i = start; i <= A.size()-k; i++)
helper(A, k-1, i+1, target - A[i], ans);
}
int solutionKSum(vector A,int k,int target) {
int ans = 0;
helper(A, k, 0, target, ans);
return ans;
}
请问如何用DP降低复杂度？ | u****x
发帖数: 97 | 2 可以先排序 然后一旦target
这样可以提速一点 | d****n
发帖数: 233 | 3 好像还是不行。 http://lintcode.com/en/problem/k-sum/
【在 u****x 的大作中提到】
: 可以先排序 然后一旦target: 这样可以提速一点
| d****n
发帖数: 233 | 4 试着用DP如下：
int solutionKSum(vector A,int k,int target) {
int n = A.size();
vector>> map(n+1, vector>(k+1, vector
(target+1, 0)));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= min(i, k); j++) {
if (j == 1) {
if (A[i-1] <= target)
map[i][1][A[i-1]] = 1;
}
else{
for(int p = 1; p <= target; p++) {
if (A[i-1] <= p)
map[i][j][p] = map[i][j-1][p-A[i-1]] + map[i-1][j][
p];
}
}
}
return map[n][k][target];
}
结果是：
Input
[1,4,7,10,12,15,16,18,21,23,24,25,26,29], 5, 113
Output 11
Expected 9
哪位大牛帮看看错在哪里？
【在 d****n 的大作中提到】
: 好像还是不行。 http://lintcode.com/en/problem/k-sum/
| m*****k
发帖数: 731 | 5 why 不行?
n distinct positive integers, 不就是暗示可以先排序么？
【在 d****n 的大作中提到】
: 好像还是不行。 http://lintcode.com/en/problem/k-sum/
| k*******a
发帖数: 433 | 6 能否说一下你的动态规划思路呢？
vector
【在 d****n 的大作中提到】
: 试着用DP如下：
:
: int solutionKSum(vector A,int k,int target) {
: int n = A.size();
:
: vector>> map(n+1, vector>(k+1, vector
: (target+1, 0)));
:
: for(int i = 1; i <= n; i++)
: for(int j = 1; j <= min(i, k); j++) {
| b******t
发帖数: 9 | | r****7
发帖数: 2282 | 8 这个题用DP将是关于target的NP问题
其实不用DP也是关于k的NP问题
我觉得不如暴力A(k, n)的算
vector
【在 d****n 的大作中提到】
: 试着用DP如下：
:
: int solutionKSum(vector A,int k,int target) {
: int n = A.size();
:
: vector>> map(n+1, vector>(k+1, vector
: (target+1, 0)));
:
: for(int i = 1; i <= n; i++)
: for(int j = 1; j <= min(i, k); j++) {
| r****7
发帖数: 2282 | 9 你要记住start和end两个index，方程应该是
dp[target][k][s][e] = dp[target - i][kk][s][m] * dp[i][k - kk][m + 1][e]
遍历i, k, s 和 e
不过感觉真的很难写，我还是觉得该用暴力解。等回去看看
vector
【在 d****n 的大作中提到】
: 试着用DP如下：
:
: int solutionKSum(vector A,int k,int target) {
: int n = A.size();
:
: vector>> map(n+1, vector>(k+1, vector
: (target+1, 0)));
:
: for(int i = 1; i <= n; i++)
: for(int j = 1; j <= min(i, k); j++) {
| d****n
发帖数: 233 | 10 map[i][j][k] is the total number of combinations by selecting j number of
elements from first i elements in the array and the sum of these j elements
is k.
BTW, I've figured out the bug in my code.
【在 k*******a 的大作中提到】
: 能否说一下你的动态规划思路呢？
:
: vector
| x****3
发帖数: 62 | | d****n
发帖数: 233 | |
|
