leetcode416. 分割等和子集

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-equal-subset-sum

题目描述

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

示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100

暴力递归

动态规划其实是对暴力递归的改写,当你对动态规划没有思路时,要先写出暴力递归的尝试,
这道题是典型的 0 -1 背包问题,就是要组成目标和,那我们每到一个位置,都是面临两个选择,选或者不选.分别对两种情况进行递归,最后比较两种递归的情况就可以得到答案了.
还要注意找到base case ,我们代码里注释说明

代码演示

    public boolean canPartition(int[] nums) {if(nums.length == 1){return false;}//计算数组累加和int sum = 0;for(int i = 0 ; i < nums.length;i++){sum += nums[i];}//如果不是偶数没有办法拆分成两个数组和相等if(sum % 2 != 0){return false;}//能找到拆分方式的数量如果不等于0 ,就是可以拆分return process(nums,sum / 2,0) != 0;}/*** 暴力递归* 计算有多少种拆分方式* target 要组成的目标数字* index 来到的下标位置*/public int process(int[]nums,int target,int index){//base case 如果来到越界位置,target == 0,前面选择有效,返回1,代表一种有效方案if(index == nums.length){return target == 0 ? 1 : 0;}//target < 0 说明前面的选择是无效的,返回 0if(target < 0){return 0;}// target == 0 ,前面选择是合法的,返回1.if(target == 0){return 1;}//经典背包解法,选和不选两种情况 //不选时 去 index + 1 位置继续做选择int p1 = process(nums,target,index + 1);//选时 去 index + 1 位置继续做选择,需要组成的数字还剩target - nums[index]int p2 = process(nums,target - nums[index],index + 1);//返回最多的方法数return Math.max(p1,p2);}

动态规划

解题思路

动态规划是对暴力递归的改写,三个步骤,
1.根据base case 初始化dp表
2.递归过程改成从dp 表种拿值得过程
3.返回递归调用得最初始状态,
具体这个问题种,位置如何依赖,如何拿值呢,我用图演示下.
横着得方向是target,竖得方向是index,(演示需要认为数组长度是7,)
首先看,根据base case ,target == 0 时,返回1,所以dp 表种,target = 0 位置,全部初始化为1.
base case 里index 越界时,target = 0 时是1,其余是0,因为java语言本身数组初始化时,元素都是0,所以只需要初始化1出来就好了.
再看一般位置如何求解,以x位置为例.在递归中;
int p1 = process(nums,target,index + 1);
//选时去 index + 1 位置继续做选择,需要组成的数字还剩target - nums[index]
int p2 = process(nums,target - nums[index],index + 1);
看到,x 依赖,index + 1 位置,正下方(i+ 1,target)的位置,和(target - nums[index],index + 1)这两个位置以五角星位置参考,

  >  所以得出状态转移方程:dp[i][j] = Math.max(dp[i + 1][j] ,dp[i + 1][target - nums[index]]);

代码演示

    /*** 动态规划* @param nums* @return*/public boolean dp(int[] nums){int sum = 0;for(int i = 0 ; i < nums.length;i++){sum += nums[i];}if(sum % 2 != 0){return false;}int N  = nums.length;int target = sum / 2;//动态规划表int[][]dp = new int[N+1][target+ 1];//初始化 target == 0 时的位置为1.for (int i = 0; i <= N ; i++){dp[i][0] = 1;}for(int i = N - 1;i >= 0;i--){for (int j = 0; j <= target;j++){int p1 = dp[i + 1][j];int p2 = 0;//判断位置不能越界if(j - nums[i] >= 0){p2 = dp[i+1][j - nums[i] ];}//状态转移方程dp[i][j] = Math.max(p1,p2);}}return dp[0][target] != 0;}