LintCode刷题——背包问题 IV（动态规划）

 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 }