代码随想录二刷 Day 44

代码随想录二刷 Day 44"/>

代码随想录二刷 Day 44

01背包问题二维做法先遍历背包或者物品都可以，然后是前序遍历；

一维做法一定先遍历物品然后遍历背包，遍历背包的时候是后序遍历；一维做法还是有点难理解，其实就是后面的数字还是要从前面的推导出来，但是如果正序的话前面的数据已经被覆盖了用不了了，所以就倒序； 另一方面由于初始化得当，倒序也可以把第一层算出来，然后第二次倒序的时候在还没改变前面数值的时候调用上一层的结果，这个上层结果其实也是这层前面得数；

416. 分割等和子集

 下面这个判断是否符合条件没想到，其他部分写的和答案差不多

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;int target = 0;for (int i = 0; i < nums.size(); i++){sum += nums[i];}if (sum %2 == 1) return false;target = sum/2;  //这个就是背包容量j，重量为元素的数值，价值也为元素的数值//vector<int> dp(target, 0); 这么写溢出或者越界vector<int> dp(target + 1, 0);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]);}}if (dp[target] == target) return true;return false;}
};