lintcode 89. K数之和【背包】

89. K数之和中文English给定n个不同的正整数整数kkn以及一个目标数字target。在这n个数里面找出k个数使得这k个数的和等于目标数字求问有多少种方案样例样例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输入测试数据 (每行一个参数)如何理解测试数据不用纠结ij的大小关系 单独考虑每层循环即可记得memset 虽然不懂为啥都是单独的函数内部的 还会出现多组数据j也是倒序 与容量倒序同理class Solution { public: /** * param A: An integer array * param k: A positive integer (k length(A)) * param target: An integer * return: An integera */ int kSum(vectorint A, int k, int target) { // write your code here int n A.size(); int dp[1000][1000]; memset(dp,0,sizeof(dp)); dp[0][0] 1; for (int i 0; i n; i ) { for (int j k; j 0; j --) { for (int t target; t A[i]; t --) { dp[j][t] dp[j-1][t-A[i]]; } } } return dp[k][target]; } };