网站推广邮箱怎么做,网站推广营销效果,数字广东网络建设有限公司介绍,企业做网站大概多少钱目录 一、分割等和子集-LeetCode 416思路实现代码1.二维dp代码2.一维dp代码 问题总结 一、分割等和子集-LeetCode 416
Leecode链接: leetcode 416 文章链接: 代码随想录 视频链接: B站
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例1
输入nums [1,5,11,5]
输出true
解释数组可以分割成 [1, 5, 5] 和 [11] 。思路
本体可以看作一个背包模型将数组总和除2将总和一半定义为背包的容量数组元素为可选的物品。本题既可以定义一个一维dp数组也可以定义一个二维dp数组但二维便于理解与讲解并且一维只是二维的精简版思想基本一致所以主要写一下二维的思路。数组形式为dp[i][j]i为可选的物品范围例如当i为3时表示可选的物品范围为0到3下标的物品任意物品j表示当前背包的容量大小。dp数组含义为在j容量下物品0到i范围可以获得的最大和。递推公式为dp[i][j] dp[i-1][j]或dp[i][j] max(dp[i-1][j] , dp[i-1][j-nums[i]] nums[i])。前者表示不放的情况后者表示物品放入后可能的情况。不放的条件就是背包容量不足以放下物品放物品的条件就是当前背包的容量大于或等于当前物品的重量。
实现代码
1.二维dp代码
//cpp
class Solution {
public:bool canPartition(vectorint nums) {int sum 0;int len nums.size();//物品的数量for(int a:nums){sum a;} if(sum%2 1) return false;int target sum/2;//既是物品的价值也是物品的重量vectorvectorintdp(len,vectorint(target1,0));for(int j nums[0];jtarget;j){dp[0][j] nums[0];}for(int i 1;ilen;i){for(int j 0;jtarget;j){if(jnums[i]){dp[i][j] dp[i-1][j];}else {dp[i][j] max(dp[i-1][j],dp[i-1][j - nums[i]]nums[i]);}}}if(dp[len-1][target] target) return true;return false;}
};2.一维dp代码
//cpp
class Solution {
public:bool canPartition(vectorint nums) {//vectorint dp(10001, 0);int sum 0;for(int a:nums){sum a;} if(sum%2 1) return false;int t sum/2;vectorintdp(t1,0);for(int i 0;inums.size();i){for(int j t;jnums[i];j--){dp[j] max(dp[j],dp[j-nums[i]]nums[i]);}}if(dp[t] t) return true;return false;}
};问题
代码实现细节不熟练比如初始化时怎么将第一行的哪些数初始化为恒定值。
总结
一维与二维的区别在于省去了多余空间的使用并且改变了遍历顺序这是因为如果跟二维数组一样从前往后遍历就会导致重复选择同一个物品。比如当i 1时dp[1] 1、dp[2] 1;当i 2时dp[1] 1、dp[2] 2显然是不对的因为一件物品只能选一次。虽然一维省去了空间但时间复杂很高leetcode上一维dp的执行用时为300ms左右空间占用达到了10MB左右二维dp为100ms左右同样的二维空间占用达到了98MB左右。
