LintCode 563. 背包问题 V（DP）
1. 题目
作者：Michael阿明
给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。
每一个物品只能使用一次
样例
给出候选物品集合 [1,2,3,3,7] 以及 target 7
结果的集合为:
[7]
[1,3,3]
返回 2
2. 解题
dp[i][j]dp[i][j]dp[i][j] 表示第 i 个物品下，重量为 j 的方案数
class Solution {
public:
int backPackV(vector &nums, int target) {
if(nums.size() == 0)
return 0;
if(target == 0)
return 1;
int n = nums.size(), i, j;
vector<vector> dp(n,vector(target+1, 0));
dp[0][0] = 1;//第一个物品不放
if(nums[0] <= target)
dp[0][nums[0]] = 1;//第一个物品放，1种方案
for(i = 1; i < n; i++)//遍历剩余的物品
{
for(j = 0; j <= target; j++)
{
if(dp[i-1][j] != 0)//上一行所有存在的状态
{
dp[i][j] += dp[i-1][j];//i个物品不放
if(j <= target-nums[i])//i个物品放进去不超重
dp[i][j+nums[i]] += dp[i-1][j];
}
}
}
return dp[n-1][target];
}
};
当前行状态只依赖于上一行，可以进行状态压缩，节省存储空间，代码略。
100% 数据通过测试
总耗时 201 ms
您的提交打败了 45.80% 的提交!
作者：Michael阿明
