题目链接

分割等和子集

题目描述

image.png

解题思路

可以看成是背包问题：从n个物品中选取m个物品，每个物品只能选择一次，每个物品的价值对应p，是否能恰好选出价值和为k的选法；

记dp[i][j] 表示 是否能从前i个物品中恰好选择价值和为j的选法；对于每个物品而言，只有两种情况：选和不选，因此状态转移方程为：

  1. if(当前物品i价值 > j) {
  2.     // 不选择i，往前走
  3.     dp[i][j] = dp[i-1][j];
  4. } else{
  5.     // 选择i，往前走 | 不选择i，往前走  两者都可以进行判断取或
  6.     dp[i][j] = dp[i-1][j] | dp[i-1][j-1];
  7. }

实现代码：

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  4.         int len = nums.length;
  5.         int sum = nums[0];
  6.         int max = sum;
  7.         for (int i = 1; i < len; i++) {
  8.             sum += nums[i];
  9.             max = max > nums[i] ? max : nums[i];
  10.         }
  11.         if (sum % 2 != 0) {
  12.             return false;
  13.         }
  15.         int target = sum / 2;
  16.         if (target < max) {
  17.             return false;
  18.         }
  20.         boolean[][] dp = new boolean[len][target + 1];
  22.         for (int i = 0; i < len; i++) {
  23.             dp[i][0] = true;
  24.         }
  25.         dp[0][nums[0]] = true;
  27.         for (int i = 1; i < len; i++) {
  28.             int val = nums[i];
  29.             for (int j = 1; j <= target; j++) {
  30.                 if (j >= val) {
  31.                     dp[i][j] = dp[i - 1][j - val] || dp[i - 1][j];
  32.                 } else {
  33.                     dp[i][j] = dp[i - 1][j];
  34.                 }
  35.             }
  36.         }
  38.         return dp[len - 1][target];
  39.     }
  40. }