原题

LintCode 564. Backpack VI

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();
    }
};