力扣小白刷题之416题分割等和子集_力扣416一维数组为什么从后往前更新

题目描述

给定一个只包含正整数的非空数组，是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意：

1. 每个数组中的元素不会超过100
2. 数组的大小不会超过200

问题分析

参考自：https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/0-1-bei-bao-wen-ti-bian-ti-zhi-zi-ji-fen-ge-by-lab/

这个问题，初看与背包没有任何关系，为什么说它是背包问题呢？
首先回忆一下背包问题的大致描述是什么：

• 给你一个可装载重量为 W 的背包 和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

那么对于这个问题，我们可以先对集合求和，得出 sum，把问题转化为背包问题：

• 给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为 nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？

解法分析

第一步要明确两点：【状态】和【选择】

• 状态就是【背包的容量】和【可选择的物品】
• 选择就是【装进背包】和【不装进背包】

第二步要明确 dp 数组的定义

• 按照背包问题的套路，可以给出如下定义：
  • dp[i][j] = x 表示，对于前 i 个物品，当前背包的容量为 j 时，若 x 为 true，则说明可以恰好将背包装满，若 x 为 false，则说明不能恰好将背包装满。
  • 比如说，dp[4][9] = true，其含义为：对于容量为 9 的背包，若只是用前 4 个物品，可以有一种方法把背包恰好装满。
  • 或者说对于本题，含义是对于给定的集合中，若只对前 4 个数字进行选择，存在一个子集的和可以恰好凑出 9。
  • 根据这个定义，我们想求的最终答案就是 dp[N][sum / 2]，
  • base case 就是 dp[…][0] = true 和 dp[0][…] = false，因为背包没有空间的时候，就相当于装满了，而当没有物品可选择的时候，肯定没办法装满背包。

第三步，根据【选择】，思考状态转移的逻辑
回想刚才的 dp数组含义，可以根据【选择】对 dp[i][j] 得到以下状态转移：

• 如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么是否能够恰好装满背包，取决于上一个状态 dp[i - 1][j]，继承之前的结果。
• 如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么是否能够恰好装满背包，取决于状态 dp[i - 1][j - nums[i - 1]]。
  • 注意：由于 i 是从 1 开始的，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i - 1]，这一点不要搞混。
• 换句话说，如果 j - nums[i - 1] 的重量可以被恰好装满，那么只要把第 i 个物品装进去，也可恰好装满 j 的重量；否则的话，重量 j 肯定是装不满的。

代码

进行状态压缩

注意到 dp[i][j] 都是通过上一行 dp[i - 1][…] 转移过来的，之前的数据都不会再使用了。
所以我们可以进行状态压缩，将二维 dp 数组压缩为一维，节约空间复杂度。

状态压缩的代码和之前的解法思路完全相同，只在一行 dp数组上操作，i 每进行一轮迭代，dp[j] 其实就相当于 dp[i][j]，所以只需要一维数组就够用了。(第 i 次循环结束后 dp[j] 表示的就是我们定义的状态 dp[i][j])
唯一需要注意的是 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。 (参考背包九讲)

时间复杂度： O(n*sum)
空间复杂度： O(sum)

---

其他细化解法

参考自：https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/0-1-bei-bao-wen-ti-xiang-jie-zhen-dui-ben-ti-de-yo/

等价转换：是否可以从这个数组中挑选出一些正整数，使得这些数的和等于整个数组元素的和的一半。 前提条件是：数组的和一定得是偶数，即数组的和一定得被2整除，这一点是特判。

本题与 0 - 1 背包问题有一个很大的不同，即：

• 0 - 1 背包问题选取的物品的容积总量不能超过规定的总量(背包容量)；
• 本题选取的数字之和需要恰好等于规定的和的一半。

这一点区别，决定了在初始化的时候，所有的值应该初始化为 false。

作为“0 - 1 背包问题”，它的特点是：“每个数只能用一次”。思路是：物品一个一个选，容量也一点一点放大考虑（这一点是“动态规划”的思想，特别重要）。

如果在实际生活中，其实我们也是这样做的，一个一个尝试把候选物品放入“背包”，看什么时候能容纳的价值最大。

具体做法是：画一个 len 行，target + 1 列的表格。这里 len 是物品的个数，target 是背包的容量。 len 行 表示一个一个物品考虑，target + 1 多出来的那 1 列，表示背包容量从 0 开始，很多时候，我们需要考虑这个容量为 0 的数值。

• 状态定义：dp[i][j] 表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。（dp数组只需要记录T/F即可）
• 状态转移方程：很多时候，状态转移方程思考的角度是“分类讨论”，对于“0 - 1 背包问题”而言就是“当前考虑到的数字选与不选”。
  1. 不选择 nums[i]，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j，那么 dp[i - 1][j] = true;
  2. 选择 nums[i]，如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。
  3. 状态转移方程是：dp[i][j] = dp[i - 1][j] or dp[i]][j - nums[i]]
  4. 一般写出状态转移方程之后，就需要考虑边界条件（一般而言也是初始化条件）。
     1. j - nums[i] 作为数组的下标，一定得保证大于等于 0，因此 nums[i] <= j;
     2. 注意到一种非常特殊的情况：j 恰好等于 nums[i]，即单独 nums[i] 这个数恰好等于此时“背包的容积” j，这也是符和题意的。
        因此完整的状态转移方程是：
        
     3. 初始化： dp[0][0] = false，因为是正整数，当然凑不出和为 0.
     4. 输出：dp[len - 1][target]，这里 len 表示数组的长度，target 是数组的元素之和（必须是偶数）的一半。

代码1

复杂度分析

• 时间复杂度：O(NC)，这里N是数组元素的个数，C是数组元素的和的一半。
• 空间复杂度：O(NC)。

代码改进

1. 修改状态数组初始化的定义 ：dp[0][0] = true。
   注意到：容量为 0 的时候，即 dp[i][0] 按照本意来说，应该设置为 false，但是注意到状态转移方程(代码中)：dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
   j - nums[i] == 0 成立的时候，根据上面分析，就说明单独的 nums[i] 这个数就恰好能够在被分割为单独的一组，其余的数分割为另外一组，因此，我们把初始化的 dp[i][0] 设置成为 true 在 代码运行层面是完全没有问题的。
2. 观察状态转移方程的特点，or 的结果只要为真，表格下面所有的值都为真，因此在填表的时候，只要表格的最后一列是 true，代码就可以结束，直接返回 true 即可。
   

继续优化

0 - 1 背包问题常规优化：“状态数组”从二维降到一维，减少空间复杂度。

• 在“填表格”的时候，当前行只参考了上一行的值，因此状态数组可以只设置 2 行，使用“滚动数组”的技巧“填表格”即可；
• 实际上连“滚动数组”都不必，在“填表格”的时候，当前行总是参考了它上面一行“头顶上”那个位置和“左上角”某个位置的值。 因此，我们可以只开一个一维数组，从后向前依次填表即可。
  （这一点第一次接触的时候可能会觉得很奇怪，理解的办法是：拿题目中的示例，画一个表格，自己模拟一遍程序是如何“填表”的行为，就很清楚为什么状态数组压缩到 1 行的时候，需要“从后往前”填表）。
• “从后往前”写的过程中，一旦 nums[i] <= j 不满足，可以马上退出当前循环，因为后面的 j 的值肯定越来越小，没有必要继续做判断，直接进入外层循环的下一层。相当于一个剪枝，这一点是“从前向后”填表所不具备的。

** 代码**

复杂度分析：

• 时间复杂度：O(NC)：这里N是数组元素的个数，C是数组元素的和的一半。
• 空间复杂度：O©：减少了物品那个维度，无论来多少个数，用一行表示状态就够了。
  补充说明：“0 - 1 背包”问题是一类非常重要的动态规划问题，一开始学习的时候，可能会觉得比较陌生，这个时候，建议要自己手动计算一下，画一个表格，模拟一遍代码的执行流程。
  这个过程是非常重要的，自己动手填过表，就能加深体会程序是如何执行的，也就能更好地理解“状态压缩”地思路和好处。

一些问题

1. 用位运算 与运算 来判断一个数是奇数还是偶数：
   1. 只需要判断最后一位是 1 还是 0
   2. 最后一位是 1 说明是奇数，是 0 说明是偶数。
   3. 因为只有 2 的 0 次方才是奇数值 1，其余 2 的 k(1, 2, … ) 都是偶数
   4. a & 1 == 1 -> 奇数 , 奇数的二进制低位一定是 1.