【算法训练 day44 分割等和子集】
目录
- 一、分割等和子集-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(vector<int>& nums) {int sum = 0;int len = nums.size();//物品的数量for(int a:nums){sum += a;} if(sum%2 == 1) return false;int target = sum/2;//既是物品的价值也是物品的重量vector<vector<int>>dp(len,vector<int>(target+1,0));for(int j = nums[0];j<=target;j++){dp[0][j] = nums[0];}for(int i = 1;i<len;i++){for(int j = 0;j<=target;j++){if(j<nums[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(vector<int>& nums) {//vector<int> dp(10001, 0);int sum = 0;for(int a:nums){sum += a;} if(sum%2 == 1) return false;int t = sum/2;vector<int>dp(t+1,0);for(int i = 0;i<nums.size();i++){for(int j = t;j>=nums[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左右。