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

动态规划：01背包理论基础

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

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

416. 分割等和子集

https://leetcode.cn/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]);}
};