分割等和子集
- leetcode416. 分割等和子集
- 题目描述
- 暴力递归
- 代码演示
- 动态规划
- 解题思路
- 代码演示
- 动态规划专题
leetcode416. 分割等和子集
题目描述
暴力递归
代码演示
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);}
动态规划
解题思路
> 所以得出状态转移方程: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;}
动态规划专题
leetcode.486. 预测赢家,动态规划
leetcode354. 俄罗斯套娃信封问题
leetcode688. 骑士在棋盘上的概率
leetcode300. 最长递增子序列
填满背包的最大价格
-数字转字符串,有多少种转化结果
本文链接：https://my.lmcjl.com/post/2515.html
展开阅读全文
4 评论