动态规划LeetCode-416.分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

01背包问题
背包问题，大家都知道，有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
01背包一维滚动数组递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题如何转换到01背包问题是关键，我们想一想，题目说分割两个等和子集，那只需要是sum/2得到一个子集的体积，这个sum/2得到的相当于就是一个背包，这个背包体积是sum/2，看nums里面能否把这个背包体积装满，如果能装满，即可以分割等和子集。对应01背包问题，这题注意的点是背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值，其次背包中每一个元素是不可重复放入。动规五部曲（dp含义、递推公式、初始化、遍历顺序、打印数组）

dp含义：dp[j]表示容量为j的背包，所背的物品价值最大可以为dp[j]。

递推公式：本题中每一个元素的数值既是重量，也是价值。所以
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

初始化：背包容量为j=0，物品最大价值为dp[0]=0这个好理解，那其他下标初始化也为0是为什么呢，因为dp数组在递推的过程中取得最大的价值，把下标初始成负无穷小，就不会被初始值覆盖，这里初始为0即可，也是一样的。

遍历顺序：
这里是用一维滚动数组来解决，所以物品遍历的for循环放在外层，遍历背包的for循环放在内层，然后题目说物品i只能放一次，所以且内层for循环倒序遍历！
因为倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

打印数组：当遇到疑惑或者提交错误时，打印数组出来比较快速的看看哪一步有错。

以下是我在力扣c语言提交的代码，仅供参考：
一维滚动数组：

bool canPartition(int* nums, int numsSize) {//给出容量和数值大小范围，求的还是一半，所以数组大小为200*100/2+1int dp[10001]={0};int sum = 0;int target = 0;for(int i = 0;i<numsSize;i++){sum+= nums[i];}//如果总和为偶数说明可以分割等和子集，反之if(sum % 2 == 0){target = sum / 2;}else if(sum % 2 != 0){return false;}//初始化memset(dp,0,sizeof(dp));dp[0] = 0;//先遍历物品for(int i = 0;i<numsSize;i++){//再遍历背包，且是倒序遍历，保证物品i只被放入一次！for(int j = target;j>=nums[i];j--){//01背包递推公式dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);//本题中每一个元素的数值既是重量，也是价值dp[j] = dp[j] > dp[j-nums[i]] + nums[i] ? dp[j] : dp[j-nums[i]] + nums[i];}}//如果dp[target] == target//说明可以将这个数组分割成两个子集，使得两个子集的元素和相等。if(dp[target] == target) return true;return false;
}

在此也给出二维数组的求解：
 

bool canPartition(int* nums, int numsSize) {int sum = 0;for(int i = 0;i<numsSize;i++){sum += nums[i];}if(sum % 2 == 1){return false;}int traget = sum / 2;int dp[numsSize+1][traget+1];memset(dp,0,sizeof(dp));for(int i = nums[0];i<=traget;i++){dp[0][i]=nums[0];}for(int i = 1;i<numsSize;i++){for(int j = 0;j<=traget;j++){if(j<nums[i]){dp[i][j] = dp[i-1][j];}else{dp[i][j] = dp[i-1][j] > (dp[i-1][j-nums[i]]+nums[i]) ? dp[i-1][j]: (dp[i-1][j-nums[i]]+nums[i]);}}}if(dp[numsSize-1][traget] == traget){return true;}else{return false;}
}