算法-动态规划（四）
⚠️今天往后的几篇文章，我们会讨论动态规划里一个经典的问题【背包问题】，有关背包问题，希望大家可以自行百度一下【背包九问】去了解思考一下，涉及其中的背包、容量等的概念问题，在系列文章里不会写，所以还是希望大家先去了解一下这些概念。
👉👀💬今日练习（一）分割等和子集（LeetCode-416）。
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。举例：
输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11].输入: [1, 2, 3, 5]输出: false解释: 数组不能分割成两个元素和相等的子集.
🙋解法一：
🙇思路：
我们先对这个问题进行一下等价转换：数组要分割成两个等和子集，那么这个数组一定具有以下特点：
数组的总和为偶数，如果总和为奇数，我们也就没必要再往下计算了。
两个子集的和一定等于数组总和的一半。
基于上面两个特点，我们对这道题也就算是最基本的思路打开了，下面就是0-1背包问题的分析了。
0-1背包问题中，数组中的「每个数只能取一次」。所以整体思路就是，一个一个的取数，一点一点的增加容量。
定义数组的长度为len，数组总和的一半为target，此题具体做法如下：我们定义一个行为len，列为target+1的二维数组dp；
状态定义：dp[i][j]表示，我们可以从0~i区间内选择一些数使得这些数的和恰等于j。
转态转移：
当选择nums[i]时，在[0 , i-1]这个区间内能找到一些数，这些数的和为j-nums[i]，这时dp[i][j]=dp[i-1][j-nums[i]]。
当不选择nums[i]时，在[0 , i-1]这个区间内已经有一些数，这些数的和为j，这时dp[i][j] = true。
此题中的状态转移方程：
dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i]]
继续分析，有了数组，那么数组下标一定得大于0；所以j-nums[i]>0，nums[i]<=j。当nums[i]=j时，dp[i][j]=true。
代码：
public boolean canPartition(int[] nums) {int len= nums.length;if(len<1){return false;}int sum=0;for(int num:nums){sum+=num;}//sum为奇数返回false。if((sum &1)==1){return false;}int target = sum/2;boolean[][] dp = new boolean[len][target+1];if(nums[0]<target){dp[0][nums[0]]=true;}for(int i=1;i<len;i++){for(int j=0;j<=target;j++){dp[i][j]=dp[i-1][j];if(nums[i]==j){dp[i][j]=true;continue;}if(nums[i]<j){dp[i][j] = dp[i-1][j]||dp[i-1][j-nums[i]];}}}return dp[len-1][target];}
复杂度分析
时间复杂度：O(NC)：这里N 是数组元素的个数，C 是数组元素的和的一半。
空间复杂度：O(NC)。
🙋解法二：对上面解法一进行优化。
🙇思路：
在上面解法一中，根据状态定义我们可以得到dp[0][0]=false;因为我们找不到一个正整数可以使其等于0。
但是当j==nums[i]时，j-nums[i]==0是成立的，nums[i]这个数可以被单独划分为一个子集。因此我们把dp[0][0]设为true也是合理。虽然不符合状态定义，但是从状态转移来说是完全符合的。
根据状态转移方程，dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i]]，我们可以得到，当二维数组dp的最后一列dp[i][target]为true时，当前列下面的的值一定都是true，这时候我们就可以提前结束遍历了，直接返回true。
代码：
public boolean canPartition_1(int[] nums) {int len = nums.length;if (len < 1) {return false;}int sum = 0;for (int num : nums) {sum += num;}//sum为奇数返回false。if ((sum & 1) == 1) {return false;}int target = sum / 2;boolean[][] dp = new boolean[len][target + 1];//初始化成为 true 虽然不符合状态定义，但是从状态转移来说是完全可以的dp[0][0] = true;if (nums[0] == target) {dp[0][nums[0]] = true;}for (int i = 1; i < len; i++) {for (int j = 0; j <= target; j++) {dp[i][j] = dp[i - 1][j];//因为有dp[0][0]=true的q前提，所以这儿可以将解法一中//<=的q情况合起来写，不必分开判断。if (nums[i] <= j) {dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];}}//根据我们上面的分析，这儿可以提前结束。if(dp[i][target]){return true;}}return dp[len-1][target];}
🙋解法三：对进行两个解法的空间优化。
🙇思路：
一般情况下对0-1背包问题的空间优化就是将二维数组降维成一位数组。
我们基于对上面两个解法的思路，做一些思考：
上面解法中，我们每次的循环里都只用到了上面一行的数据，而且只用到了上面一行同一列的数据和上面一行左边某个位置的数据。
我们采用「滚动数组」的方式来进行「填表」。
这儿我们定义一个一维数组dp，长度为target+1，从后向前依次填表。
从后向前填表的过程，如果碰到不满足j>=nums[i]，也就不必要继续进行了，可以马上退出循环，因为要保证dp[j-nums[i]]下标合法。
思考：为什么要从后向前逆序填表？
这是因为在一维的情况下，根据dp[j] || dp[j-nums[i]]来推dp[j]的值，我们需要保证数组中前面的值不能对后面的值有影响，举个例子，给定数组并采用采用正序填表：
[]，target=6，nums[0]<= 6 ; dp[2]=True当i=0, j=4时，dp[4] = dp[4] || dp[2] =True;i不变，这时继续向后遍历，j=6时，dp[6] = dp[6]||dp[6-2]= True;这显然就已经错了。dp中q前面的值影响了后边的值。
所以，在这儿我要采用逆序填表，消除同一行前面对后面产生的影响。
代码：
public boolean canPartition_2(int[] nums) {int len = nums.length;if (len < 1) {return false;}int sum = 0;for (int num : nums) {sum += num;}//sum为奇数返回false。if ((sum & 1) == 1) {return false;}int target = sum / 2;boolean[] dp = new boolean[target + 1];dp[0] = true;if (nums[0] <= target) {dp[nums[0]] = true;}for (int i = 1; i < len; i++) {for (int j = target; j >= nums[0]; j--) {if(dp[target]){return true;}dp[j]=dp[j]||dp[j-nums[i]];}}return dp[target];}
复杂度分析
时间复杂度：O(NC)：这里N 是数组元素的个数，C 是数组元素的和的一半。
空间复杂度：O(C)。
不积跬步，无以至千里。
文章有帮助的话，点个转发、在看呗
。
谢谢支持哟 (*^__^*)
END
👇