赞
踩
给你一个 只包含正整数 的 非空 数组 nums
。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。
1 <= nums.length <= 200
1 <= nums[i] <= 100
bool canPartition(vector<int>&nums) { //对数组的初始情况进行判断 if(nums.empty()) { return false; } int length=nums.size(); int sum=0; //计算数组中所有的元素的总和,若总和为奇数就代表该数组无法被分割成两个等和子集 for(int num:nums) { sum+=num; } if(sum%2==1) { return false; } //因此设置目标值为sum/2,因为只要数组的一部分子集满住总和的一半,另一部分自然而然也能满足 int target=sum/2; //创建动态规划数组,行,代表数组内元素的索引,列,代表目标值 vector<vector<bool>>dp(length,vector<bool>(target+1)); //对动态规划数组进行初始化 //先填表格中的第0行,因为第一个数只能让容积为他的背包恰好被装满 if(nums[0]<=target) { dp[0][nums[0]]=true; } //建立动态规划的状态转移方程 for(int i=1;i<length;i++) { for(int j=0;j<=target;j++) { // 由题意分析出来,状态转移方程为 //dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i]] 其中如果nums[i]=j,直接便可返回true dp[i][j]=dp[i-1][j]; if(nums[i]==j) { dp[i][j]=true; continue; } if(nums[i]<j) { dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]]; } } } return dp[length-1][target]; }
//修改动态转移方程 bool canPartition2(vector<int>&nums) { //对数组的初始情况进行判断 if(nums.empty()) { return false; } int length=nums.size(); int sum=0; //计算数组中所有的元素的总和,若总和为奇数就代表该数组无法被分割成两个等和子集 for(int num:nums) { sum+=num; } if(sum%2==1) { return false; } //因此设置目标值为sum/2,因为只要数组的一部分子集满住总和的一半,另一部分自然而然也能满足 int target=sum/2; //创建动态规划数组,行,代表数组内元素的索引,列,代表目标值 vector<vector<bool>>dp(length,vector<bool>(target+1)); //对动态规划数组进行初始化 //初始化dp[0][0]=true; dp[0][0]=true; //先填表格中的第0行,因为第一个数只能让容积为他的背包恰好被装满 if(nums[0]<=target) { dp[0][nums[0]]=true; } //建立动态规划的状态转移方程 for(int i=1;i<length;i++) { for(int j=0;j<=target;j++) { // 由题意分析出来,状态转移方程为 //dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i]] 其中如果nums[i]=j,直接便可返回true dp[i][j]=dp[i-1][j]; if(nums[i]<=j) { dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]]; } } } return dp[length-1][target]; }
// 优化空间 //将状态数组从二维优化成一维 //修改动态转移方程 //从后往前遍历进行实现 bool canPartition3(vector<int>&nums) { //对数组的初始情况进行判断 if(nums.empty()) { return false; } int length=nums.size(); int sum=0; //计算数组中所有的元素的总和,若总和为奇数就代表该数组无法被分割成两个等和子集 for(int num:nums) { sum+=num; } if(sum%2==1) { return false; } //因此设置目标值为sum/2,因为只要数组的一部分子集满住总和的一半,另一部分自然而然也能满足 int target=sum/2; //创建动态规划数组,行,代表目标值 vector<bool>dp(target+1); //对动态规划数组进行初始化 //初始化dp[0][0]=true; dp[0]=true; //先填表格中的第0行,因为第一个数只能让容积为他的背包恰好被装满 if(nums[0]<=target) { dp[nums[0]]=true; } //建立动态规划的状态转移方程 for(int i=1;i<length;i++) { for(int j=target;nums[i]<=j;j--) { // 由题意分析出来,状态转移方程为 //dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i]] 其中如果nums[i]=j,直接便可返回true if(dp[target]) { return true; } dp[j]=(dp[j]||dp[j-nums[i]]); } } return dp[target]; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。