问一道题k Sum - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道题k Sum

问一道题k Sum# JobHunting - 待字闺中

d*n2014-12-01 08:12

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*x2014-12-01 08:12

2 楼

可以先排序然后一旦target这样可以提速一点

d*n2014-12-01 08:12

3 楼

好像还是不行。 http://lintcode.com/en/problem/k-sum/

【在 u****x 的大作中提到】

: 可以先排序然后一旦target: 这样可以提速一点

d*n2014-12-01 08:12

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*k2014-12-01 08:12

5 楼

why 不行?
n distinct positive integers, 不就是暗示可以先排序么？

【在 d****n 的大作中提到】

: 好像还是不行。 http://lintcode.com/en/problem/k-sum/

k*a2014-12-01 08:12

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*t2014-12-01 08:12

7 楼

dfs不犹豫

r*72014-12-01 08:12

8 楼

这个题用DP将是关于target的NP问题
其实不用DP也是关于k的NP问题
我觉得不如暴力A(k, n)的算

vector

【在 d****n 的大作中提到】

r*72014-12-01 08:12

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 的大作中提到】

d*n2014-12-01 08:12

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