免费养殖网站模板,Wordpress 悬浮菜单,信息发布网站设计,网络推广发帖网站动态规划#xff1a;01背包理论基础
动态规划#xff1a;01背包理论基础#xff08;滚动数组#xff09;
以上两个问题的代码未本地化保存
416. 分割等和子集
https://leetcode.cn/problems/partition-equal-subset-sum/
复杂的解法
class Solution {
public:bool ca…动态规划01背包理论基础
动态规划01背包理论基础滚动数组
以上两个问题的代码未本地化保存
416. 分割等和子集
https://leetcode.cn/problems/partition-equal-subset-sum/
复杂的解法
class Solution {
public:bool canPartition(vectorint nums) {int sum 0;for (int i 0; i nums.size(); i) {sum nums[i];}if (sum % 2) return false;vectorvectorbool dp(nums.size(), vectorbool(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(vectorint nums) {int sum accumulate(nums.begin(), nums.end(), 0);if (sum % 2) return false;vectorint 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]);}
};
