原题
Description
Given an integer array nums with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Notice
A number in the array can be used multiple times in the combination.
Different orders are counted as different combinations.
Example
Given nums = [1, 2, 4], target = 4
The possible combination ways are:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]
return 6
解题
动态规划问题。既然这道题叫做backpack，我们就按照背包问题来思考。那么本道题的意思就是，有多个物品，每个物品数量不受限制，求出所有能够填满背包的组合。
维护一个数组dp，其中dp[i]表示，填满容量未i的背包的所有物品组合。那么我们可以得知dp[0] = 1，及一个容量为0的背包只有一种方法可以填满：啥都不放。
那么我们可以考虑容量为i的背包，对于每一个物品n，如果背包的容量足以放入这个物品，那么问题就转换为对于一个容量为i - n的背包有多少种组合方式。即dp[i - n]
dp[i] = dp[i - nums[0]] + dp[i - nums[1]] + ... + dp[i - nums[N]]
代码
class Solution {
public:
/*
* @param nums: an integer array and all positive numbers, no duplicates
* @param target: An integer
* @return: An integer
*/
int backPackVI(vector<int> &nums, int target) {
// write your code here
vector<int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (num <= i) {
dp[i] += dp[i - num];
}
}
}
return dp.back();
}
};
