0/1背包

图片.png
image.png

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

  1. public boolean canPartition(int[] nums) {
  2.       int n = nums.length;
  3.       int sum = 0;
  4.       for (int num : nums) {
  5.         sum += num;
  6.       }
  8.       int m = sum / 2;
  9.       if (sum % 2 != 0) {
  10.         return false;
  11.       }
  13.       // dp[i][j]表示在前i个元素中是否能选一些元素和为j
  14.       boolean[][] dp = new boolean[n + 1][m + 1];
  15.       dp[0][0] = true;
  17.       for (int i = 1; i <= n; i++) {
  18.         for (int j = 1; j <= m; j++) {
  19.           // 选该元素或者不选
  20.           if (j >= nums[i - 1]) { // 选: i-1就已经满足了 或者加上i位置刚好等于j
  21.             dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j];
  22.           } else { // 不选
  23.             dp[i][j] = dp[i - 1][j]; // 前i-1位置能否凑齐j
  24.           }
  25.         }
  26.       }
  27.       return dp[n][m];
  28.     }

空间优化

  1. public boolean canPartition(int[] nums) {
  2.     int n = nums.length;
  3.     int sum = 0;
  4.     for (int num : nums) {
  5.       sum += num;
  6.     }
  8.     int m = sum / 2;
  9.     if (sum % 2 != 0) {
  10.       return false;
  11.     }
  13.     // dp[i][j]表示在前i个元素中是否能选一些元素和为j
  14.     boolean[] dp = new boolean[m + 1];
  15.     dp[0] = true;
  17.     for (int i = 1; i < n; i++) {
  18.       for (int j = m; j >= nums[i]; j--) {
  19.         // 选该元素或者不选
  20.         dp[j] = dp[j] || dp[j - nums[i]];
  21.       }
  22.     }
  23.     return dp[m];
  24.   }

完全背包

image.png

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。 假设每一种面额的硬币有无限个。 

  1. public int change(int amount, int[] coins) {
  2.       // dp[n]表示凑齐n面额的方法数
  3.       int[] dp = new int[amount + 1];
  4.       dp[0] = 1;
  6.       for (int i = 0; i < coins.length; i++) {
  7.         for (int j = coins[i]; j <= amount; j++) {
  8.           dp[j] += dp[j - coins[i]];
  9.         }
  10.       }
  11.       return dp[amount];
  12.     }