Description

Given n items with size nums[i] which is an integer array and all positive numbers, no duplicates. An integer target denotes the size of a backpack. Find the number of possible fill the backpack.

Each item may be chosen unlimited number of times.

Example

Given candidate items [2,3,6,7] and target 7, A solution set is: [7], [2, 2, 3]. return 2

Solution

与Backpack III很像，区别是III是取最大值求最优解，这一题是相加计数，初始状态基为dp[0] = 1

public class Solution {
    /**
     * @param nums an integer array and all positive numbers, no duplicates
     * @param target an integer
     * @return an integer
     */
    public int backPackIV(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 0; i 
<
 nums.length; i++) {
            for (int j = nums[i]; j 
<
= target; j++) {
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}