We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; // dp[i]中的i表示背包内总和 // 题目中说:每个数组中的元素不会超过 100,数组的大小不会超过 200 // 总和不会大于20000,背包最大只需要其中一半,所以10001大小就可以了 vector<int> dp(10001, 0); // 这个大小初始化为10001,受限于条目条件, 可以调整为sum/2,当然,这里的代码顺序需要调整一下 for (int i = 0; i < nums.size(); i++) { sum += nums[i]; } // 也可以使用库函数一步求和 // int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % 2 == 1) return false; int target = sum / 2; // 开始 01背包 for(int i = 0; i < nums.size(); i++) { for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入,所以从大到小遍历 dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); } } // 集合中的元素正好可以凑成总和target if (dp[target] == target) return true; return false; } };
代码改动如下:
class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; // dp[i]中的i表示背包内总和 for (int i = 0; i < nums.size(); i++) { sum += nums[i]; } // 也可以使用库函数一步求和 // int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % 2 == 1) return false; int target = sum / 2; // 这里初始化dp,也是对源代码的一个优化 vector<int> dp(target+1, 0); // 开始 01背包 for(int i = 0; i < nums.size(); i++) { for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入,所以从大到小遍历 dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); } } // 集合中的元素正好可以凑成总和target if (dp[target] == target) return true; return false; } };
The text was updated successfully, but these errors were encountered:
No branches or pull requests
代码改动如下:
The text was updated successfully, but these errors were encountered: