长春电商网站建设公司电话,企业推广是什么职业,大型网站开发语言排名,珠海婚恋网站建设市场分析文章目录题目描述思路 代码1. 动态规划 O(nc) 、O(nc)2. 结合滚动数组 O(nc)、O(c)二刷打卡第十四天#xff5e;熬夜也得把题目补上 题目描述
初看题目#xff0c;想到的思路是用记忆化DFS来找结果来着。。看了题解才知道是背包问题
思路 代码
1…
文章目录题目描述思路 代码1. 动态规划 O(nc) 、O(nc)2. 结合滚动数组 O(nc)、O(c)二刷打卡第十四天熬夜也得把题目补上 题目描述
初看题目想到的思路是用记忆化DFS来找结果来着。。看了题解才知道是背包问题
思路 代码
1. 动态规划 O(nc) 、O(nc)
参考了liweiwei的这篇题解里面给背包问题讲了一些相关知识时空复杂度 n 是 nums 的长度c 是 sum 的长度。dp[i][j]从[0, i]下标组成的数集里选取元素相加能否构成 j 。状态转移方程【[0, i - 1] 可以构成 j】| 【[0, i - 1] 可以构成 j - nums[i]】满足任一种情况都可以保证 dp[i][j] true因此这里采用 |
class Solution {public boolean canPartition(int[] nums) {// 题意转化找到一个集合满足其和等于 nums 总和的一半 sum / 2int sum 0;for(int num : nums) {sum num;}// 奇数肯定无法满足 sum / 2if(sum % 2 1) {return false;}// [0 ~ i 范围的元素][背包容量(包括0)]int target sum / 2;boolean[][] dp new boolean[nums.length][target 1];// 1. 边界第一个元素只能满足对应的容量if(nums[0] target) {dp[0][nums[0]] true;}// 2. 状态转移for(int i 1; i nums.length; i) {for(int j 0; j target; j) {// part 1: 先把上一轮的结果继承下来再说dp[i][j] dp[i - 1][j];// part 2: 状态转移方程看[0, i - 1]能不能满足 j - nums[i]再补上 nums[j]if(nums[i] j) {dp[i][j] | dp[i - 1][j - nums[i]];}}}return dp[nums.length - 1][target];}
}2. 结合滚动数组 O(nc)、O©
在1的基础上通过滚动数组来减少空间复杂度。在剑指Offer 47 礼物的最大值里也有用到这个方法。加入 if(dp[target]) 的判断实现剪枝效果可以打败98%这里为了看起来简洁就不加上了注意逆序是为了达到无后效性的效果。如果正序会导致后面的列用到的不是上一行的结果而是当前行的结果会导致出错可以画图理解一下或者看上面1提到的题解的解释
class Solution {public boolean canPartition(int[] nums) {// 题意转化找到一个集合满足其和等于 nums 总和的一半 sum / 2int sum 0;for(int num : nums) {sum num;}// 奇数肯定无法满足 sum / 2if(sum % 2 1) {return false;}// [0 ~ i 范围的元素][背包容量(包括0)]int target sum / 2;boolean[] dp new boolean[target 1];// 1. 边界第一个元素只能满足对应的容量if(nums[0] target) {dp[nums[0]] true;}// 2. 状态转移for(int i 1; i nums.length; i) {// 逆序达到无后效性的效果for(int j target; j 0; j--) {// part 1: 先把上一轮的结果继承下来再说滚动数组不用考虑// part 2: 状态转移方程看[0, i - 1]能不能满足 j - nums[i]再补上 nums[j]if(nums[i] j) {dp[j] | dp[j - nums[i]];}}}return dp[target];}
}二刷 背包 你就说你选不选吧指元素 你要能 true 我肯定选啊 O(nc)、O(nc)
class Solution {public boolean canPartition(int[] nums) {int sum 0;for(int num : nums) {sum num;}if((sum 1) 1) {return false;}// dp[i][j]从 [0, i] 的下标中能找到和为 j 的值int target sum / 2;boolean[][] dp new boolean[nums.length][target 1];if(nums[0] target) {dp[0][nums[0]] true;}for(int i 1; i nums.length; i) {for(int j 0; j target; j) {// 继承结果 当前可行dp[i][j] (dp[i - 1][j]) | (nums[i] j ? dp[i - 1][j - nums[i]] : false);}}return dp[nums.length - 1][target];}
}滚动数组逆序降低空间复杂度
class Solution {public boolean canPartition(int[] nums) {int sum 0;for(int num : nums) {sum num;}if((sum 1) 1) {return false;}int target sum / 2;boolean[] dp new boolean[target 1];if(nums[0] target) {dp[nums[0]] true;}for(int i 1; i nums.length; i) {for(int j target; j 0; j--) {dp[j] | (nums[i] j ? dp[j - nums[i]] : false);}}return dp[target];}
}
