【Leetcode-416】动态规划-分割等和子集【Leetcode-416】动态规划-分割等

2020-10-11 打卡题-动态规划

【【Leetcode-416】动态规划-分割等和子集】给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

动态转移方程：

文章图片
状态转移方程
其中 dp[i][j] 表示从数组的 [0,i] 下标范围内选取若干个正整数（可以是 0 个），是否存在一种选取方案使得被选取的正整数的和等于 j。初始时，dp 中的全部元素都是 false。

题解：

public class CanPartition { public boolean canPartition(int[] nums) { // 数组长度小于2，不能分成两堆，直接返回False if(nums.length < 2) return false; int sum = 0,max_num=0; // 计算数值总和、寻找最大数 for (int i = 0; i < nums.length; i++) { sum += nums[i]; max_num = Math.max(max_num, nums[i]); } // 总和不能平分，即无法分成两堆，直接返回False if(sum%2 == 1) return false; // 平均数小于最大数字，说明包含负数，不符合题意，直接返回False if(max_num > sum/2) return false; // dp[i][j]: 在[0,i]范围内，nums数组能够找到若干个数字加和结果为j boolean dp[][] = new boolean[nums.length][sum/2+1]; dp[0][nums[0]] = true; for (int i = 0; i < nums.length; i++) { dp[i][0] = true; } for (int j = 1; j < sum / 2 + 1; j++) { for (int i = 1; i < nums.length; i++) { // 状态转移方程 if(j>=nums[i]) dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]; else dp[i][j] = dp[i-1][j]; } } return dp[nums.length-1][sum/2]; } public static void main(String args[]){ int nums[] = new int[]{1,2,3,6}; // true int nums2[] = new int[]{1,2,3,6,6}; // true int nums3[] = new int[]{1,2,3,5}; // false int nums4[] = new int[]{100}; // false System.out.println((new CanPartition()).canPartition(nums)); System.out.println((new CanPartition()).canPartition(nums2)); System.out.println((new CanPartition()).canPartition(nums3)); System.out.println((new CanPartition()).canPartition(nums4)); } }

附：例子[1,2,3,6]，结果返回True