力扣HOT100之动态规划：416. 分割等和子集

这道题之前刷过代码随想录，现在只能想起一点点思路，最后还是去看视频了。这道题用二维dp数组或者一维dp数组都可以做，这篇博客把两种思路都讲一下。

二维dp数组做法

原问题可以抽象为：容量为sum / 2的背包能否用数组中的物品填满？我们将重量与价值1：1转换，问题可以进一步转换为：容量为sum / 2的背包所能取到的最大价值能否达到sum / 2？
这样一来，原来的数组分割问题就变成了0-1背包问题，我们开始动规五部曲：
1.确定dp[i][j]的含义：背包容量为i的情况下，考虑下标[0 ~ j]的物品，所能取到的最大价值为dp[i][j]
2.确定递推公式 dp[i][j] = max(dp[i][j - 1], dp[i - nums[j]][j - 1] + nums[j]);
3.dp数组初始化 dp[0][j] = 0; dp[i][0] = i < nums[0] ? 0 : nums[0];
4.确定遍历顺序：先背包后物品（可以颠倒）
5.打印数组(省略)
这里并不涉及排列组合的问题，因此先遍历背包还是先遍历物品都无所谓。二维dp数组的做法有点在于便于理解，但是缺点在于复杂度过高，程序耗时较多。

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = accumulate(nums.begin(), nums.end(), 0);   //计算数组元素总和if(sum % 2 == 1) return false;   //若总和为奇数则直接跳过，一定分不出来sum /= 2;   //原问题可以抽象为：容量为sum / 2的背包能否用数组中的物品填满//将重量与价值1：1转换，可以转换为：容量为sum / 2的背包所能取到的最大价值能否达到sum / 2//1.确定dp[i][j]的含义：背包容量为i的情况下，考虑下标[0 ~ j]的物品，所能取到的最大价值为dp[i][j]//2.确定递推公式  dp[i][j] = max(dp[i][j - 1], dp[i - nums[j]][j - 1] + nums[j]);//3.dp数组初始化 dp[0][j] = 0; dp[i][0] = i < nums[0] ? 0 : nums[0];//4.确定遍历顺序：先背包后物品（可以颠倒）//5.打印数组(省略)int m = sum + 1;   //背包容量0 ~ sumint n = nums.size();   //物品0 ~ n - 1vector<vector<int>> dp(m, vector<int>(n, 0));//初始化for(int i = 0; i < m; i++)dp[i][0] = (i < nums[0] ? 0 : nums[0]);for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){if(i < nums[j]){   //背包容量为i时不足以装下物品jdp[i][j] = dp[i][j - 1];continue; }dp[i][j] = max(dp[i][j - 1], dp[i - nums[j]][j - 1] + nums[j]);if(dp[i][j] == sum) return true;}}return false;}
};

一维dp数组做法

一维dp数组实际上就是将二维dp数组压缩成了一维dp数组，在遍历顺序上非常有讲究，首先我们先给出一维dp数组的动规五部曲：
1.确定dp[i]的含义：背包容量为i的情况下，所能取到的最大价值为dp[i]
2.确定递推公式 dp[i] = max(dp[i], dp[i - nums[j]] + nums[j]);
3.dp数组初始化 dp[0] = 0;
4.确定遍历顺序：先物品后背包，背包必须倒序遍历，否则物品会重复添加（不可颠倒）
5.打印数组(省略)
在二维dp数组中，先遍历背包还是先遍历物品都是可以的，这是因为我们dp数组的推导来源于上一层或者左边，都是基于已经填好的值，那些填好的值不会再变动，因此无所谓遍历顺序，但是我们将其压缩为一维dp数组后，我们需要不断修改一维dp数组中的值，且我们每推导一次dp数组的值，都来源于二维dp数组的上一层或者左边，如果背包容量依然从小到大遍历，那么可能会出现物品被重复添加的情况，可以看一下卡哥的这期视频，有详细的反例。只有从大到小遍历背包，才能保证物品只被添加一次。至于为什么一定要先遍历物品再遍历背包，原因也很简单，我们使用一维dp数组来压缩状态，那么这个过程应该为：我们不断地增加可供添加的物品的数量，并分别讨论背包在不同容量下对于不同物品数量的情况下所能取到的最大价值，但是如果遍历顺序反过来，就变成了：我们不断减小背包的容量，并分别讨论此时背包所能装下物品的最大价值（因为是倒序遍历，背包较小的情况可能还没准备好），这就会导致计算出来的结果不对。

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = accumulate(nums.begin(), nums.end(), 0);   //计算数组元素总和if(sum % 2 == 1) return false;   //若总和为奇数则直接跳过，一定分不出来sum /= 2;   //原问题可以抽象为：容量为sum / 2的背包能否用数组中的物品填满//将重量与价值1：1转换，可以转换为：容量为sum / 2的背包所能取到的最大价值能否达到sum / 2//1.确定dp[i]的含义：背包容量为i的情况下，所能取到的最大价值为dp[i]//2.确定递推公式  dp[i] = max(dp[i], dp[i - nums[j]] + nums[j]);//3.dp数组初始化 dp[0] = 0;//4.确定遍历顺序：先物品后背包，背包必须倒序遍历，否则物品会重复添加（不可颠倒）//5.打印数组(省略)int m = sum + 1;   //背包容量0 ~ sumint n = nums.size();   //物品0 ~ n - 1vector<int> dp(m, 0);for(int j = 0; j < n; j++){for(int i = m - 1; i >= nums[j]; i--){dp[i] = max(dp[i], dp[i - nums[j]] + nums[j]);if(dp[i] == sum) return true;}}return false;}
};