代码随想录算法训练营第42天|动态规划：01背包理论基础、动态规划：01背包理论基础（滚动数组）、416.分割等

动态规划：01背包理论基础 动态规划：01背包理论基础（滚动数组）

以上两个问题的代码未本地化保存

416. 分割等和子集

leetcode /problems/partition-equal-subset-sum/

复杂的解法

class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; } if (sum % 2) return false; vector<vector<bool>> dp(nums.size(), vector<bool>(sum / 2 + 1, false)); for (int i = 0; i < nums.size(); i++) { dp[i][0] = true; } for (int j = 1; j <= sum / 2; j++) { if (j == nums[0]) dp[0][j] = true; } for (int i = 1; i < nums.size(); i++) { for (int j = 0; j <= sum / 2; j++) { if (j >= nums[i]) { dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]; } else dp[i][j] = dp[i - 1][j]; } } return dp[nums.size() - 1][sum / 2]; } };

简单的解法

class Solution { public: bool canPartition(vector<int>& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % 2) return false; vector<int> dp(sum / 2 + 1, 0); for (int i = 1; i < nums.size(); i++) { for (int j = sum / 2; j >= 0; j--) { if (j >= nums[i]) { dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); } } } return !(sum / 2 - dp[sum / 2]); } };