题目描述

给出 n 个物品, 以及一个数组, nums[i]代表第i个物品的大小, 保证大小均为正数并且没有重复, 正整数 target 表示背包的大小, 找到能填满背包的方案数。
每一个物品可以使用无数次

样例

样例1

输入: nums = [2,3,6,7] 和 target = 7
输出: 2
解释:
方案有: 
[7]
[2, 2, 3]

样例2

输入: nums = [2,3,4,5] 和 target = 7
输出: 3
解释:
方案有: 
[2, 5]
[3, 4]
[2, 2, 3]

标签 背包型动态规划    动态规划  

AC代码

 1 public class Solution {
 2     /**
 3      * @param nums: an integer array and all positive numbers, no duplicates
 4      * @param target: An integer
 5      * @return: An integer
 6      */
 7     public int backPackIV(int[] nums, int target) {
 8         // write your code here
 9         int n = nums.length;
10         int m = target;
11         if (n == 0 && m > 0) {
12             return 0;
13         }
14 
15         int[][] dp = new int[n + 1][m + 1];
16 
17         for (int i = 0; i <= n; i++) {
18             for (int j = 0; j <= m; j++) {
19                 if (i == 0 && j == 0) {
20                     dp[i][j] = 1;
21                 } else {
22                     if (i > 0) {
23                         if (nums[i - 1] > j) {
24                             dp[i][j] = dp[i - 1][j];
25                         } else {
26                             dp[i][j] = dp[i - 1][j];
27                             // 在满足k * nums[i - 1] <= j的前提下， 枚举k个
28                             for (int k = 1; k * nums[i - 1] <= j; k++) {
29                                 dp[i][j] += dp[i - 1][j - k * nums[i - 1]];
30                             }
31                         }
32                     } else {
33                         // 如果没有物品，则方案数为0
34                         dp[i][j] = 0;
35                     }
36                 }
37             }
38         }
39 
40         return dp[n][m];
41     }
42 }