前言
今天是我们讲解动态规划专题中的「背包问题」的第三天。
在众多背包问题中「01 背包问题」是最为核心的，因此我建议你先精读过 背包问题 第一讲 之后再阅读本文。
另外，我在文章结尾处列举了我所整理的关于背包问题的相关题目。
背包问题我会按照编排好的顺序进行讲解（每 2~3 天更新一篇，确保大家消化）。
你也先可以尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 DP 类型题目 ~
题目描述
这是 LeetCode 上的416. 分割等和子集，难度为 Medium。
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]. 复制代码
示例 2:
输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集. 复制代码
基本分析
基本的「将原问题抽象为 01 背包问题」的分析在 上一讲 讲过啦 ~
本节要解决的问题是：如何将「间接求解」的方式转为「直接求解」，并学习为什么能这么做，此类做法是否有共性 ...
直接求解
我们先来回顾一下 上一节 使用的「状态定义」和「转移方程」。
状态定义：
f[i][j]f[i][j]f[i][j] 代表考虑前 iii 个数值，其选择数字总和不超过 jjj 的最大价值。
转移方程：
但题目并不是问我们「最大价值是多少」，而是问「是否能凑出最大价值」。
因此我们可以对 01 背包的状态定义进行修改，使其直接与我们答案相关联：
f[i][j]f[i][j]f[i][j] 代表考虑前 iii 个数值，其选择数字总和是否恰好为 jjj。
此时 dpdpdp 数组中存储的是「布尔类型」的动规值。
相应的状态转移方程调整为：
∨∨∨ 代表逻辑「或」的意思。
新转移方程代表的意思为：想要 f[i][j]f[i][j]f[i][j] (考虑前 iii 个数值，选择的数字总和恰好为 jjj ) 为真。需要满足以下两种方案，至少一种为 truetruetrue：
1. f[i−1][j]f[i-1][j]f[i−1][j] (不选第 iii 件物品，选择的数字总和恰好为 jjj ) 为
truetruetrue
2. f[i−1][j−nums[i]]f[i-1][j-nums[i]]f[i−1][j−nums[i]] (选第 iii 件物品，选择的数字总和恰好为 jjj ) 为 truetruetrue
至此，我们利用 01 背包的基本思想，修改了「状态定义」，使其与答案直接相关联，然后根据新的「状态定义」调整了我们的「转移方程」。
但还没结束。
当我们与某个模型的「状态定义」进行了修改之后，除了考虑调整「转移方程」以外，还需要考虑修改「初始化」状态。
试考虑，我们创建的 dpdpdp 数组存储的是布尔类型，初始值都是 falsefalsefalse，这意味着无论我们怎么转移下去，都不可能产生一个 truetruetrue，最终所有的状态都仍然是 falsefalsefalse。
换句话说，我们还需要一个有效值 truetruetrue 来帮助整个过程能递推下去。
通常我们使用「首行」来初始化「有效值」。
对于本题，显然我们可以通过「先处理第一个物品」来得到「有效值」，即令 f[0][nums[0]]=truef[0][nums[0]] = truef[0][nums[0]]=true。
f[0][nums[0]]=truef[0][nums[0]] = truef[0][nums[0]]=true 代表只有容量为 nums[0]nums[0]nums[0] 的背包才符合「恰好」的要求。
但我们无法确保 nums[0]nums[0]nums[0] 不会超过我们的「最大背包」容量（也就是第一个物品过大，永远无法装入背包的情况）。
因此我们要通过处理下一行来得到有效值？或是先给物品排个序？
事实上，这里有一个技巧，就是我们增加一个「不考虑任何物品」的情况讨论。
之前我们的状态定义是 f[i][j]f[i][j]f[i][j] 代表考虑下标为 iii 之前的所有物品。现在我们可以加入不考虑任何物品的情况，也就是将「物品编号」从 0 开始调整为从 1 开始。
举个🌰，原本我们的 f[0][x]f[0][x]f[0][x] 代表只考虑第一件物品、f[1][x]f[1][x]f[1][x] 代表考虑第一件和第二件物品；调整后我们的 f[0][x]f[0][x]f[0][x] 代表不考虑任何物品、f[1][x]f[1][x]f[1][x] 代表只考虑第一件物品 ...
这种技巧本质上还是利用了「哨兵」的思想。
有了以上的分析思路，和 上一讲 的代码基础之后，我们可以很容易写出代码。
虽然更换了状态定义和转移方程，但仍然有「常规解法」、「滚动数组优化」「一维空间优化」几种实现方法。我们快速过一下。
常规解法
class Solution { public boolean canPartition(int[] nums) { int n = nums.length; //「等和子集」的和必然是总和的一半 int sum = 0; for (int i : nums) sum += i; int target = sum / 2; // 对应了总和为奇数的情况，注定不能被分为两个「等和子集」 if (target * 2 != sum) return false; // f[i][j] 代表考虑前 i 件物品，能否凑出价值「恰好」为 j 的方案 boolean[][] f = new boolean[n+1][target+1]; f[0][0] = true; for (int i = 1; i <= n; i++) { int t = nums[i-1]; for (int j = 0; j <= target; j++) { // 不选该物品 boolean no = f[i-1][j]; // 选该物品 boolean yes = j >= t ? f[i-1][j-t] : false; f[i][j] = no | yes; } } return f[n][target]; } } 复制代码
- 时间复杂度：targettargettarget 为数组总和的一半，nnn 数组元素个数。为共有 n∗targetn * targetn∗target 个状态需要被转移，复杂度为 O(n∗target)O(n * target)O(n∗target)
- 空间复杂度：O(n∗target)O(n * target)O(n∗target)
滚动数组
class Solution { public boolean canPartition(int[] nums) { int n = nums.length; //「等和子集」的和必然是总和的一半 int sum = 0; for (int i : nums) sum += i; int target = sum / 2; // 对应了总和为奇数的情况，注定不能被分为两个「等和子集」 if (target * 2 != sum) return false; // f[i][j] 代表考虑前 i 件物品，能否凑出价值「恰好」为 j 的方案 // 修改「物品维度」为 2 boolean[][] f = new boolean[2][target+1]; f[0][0] = true; for (int i = 1; i <= n; i++) { int t = nums[i-1]; for (int j = 0; j <= target; j++) { // 不选该物品 boolean no = f[(i-1)&1][j]; // 选该物品 boolean yes = j >= t ? f[(i-1)&1][j-t] : false; f[i&1][j] = no | yes; } } return f[n&1][target]; } } 复制代码
- 时间复杂度：targettargettarget 为数组总和的一半，nnn 数组元素个数。为共有 n∗targetn * targetn∗target 个状态需要被转移，复杂度为 O(n∗target)O(n * target)O(n∗target)
- 空间复杂度：O(target)O(target)O(target)
一维空间优化
class Solution { public boolean canPartition(int[] nums) { int n = nums.length; //「等和子集」的和必然是总和的一半 int sum = 0; for (int i : nums) sum += i; int target = sum / 2; // 对应了总和为奇数的情况，注定不能被分为两个「等和子集」 if (target * 2 != sum) return false; // 取消「物品维度」 boolean[] f = new boolean[target+1]; f[0] = true; for (int i = 1; i <= n; i++) { int t = nums[i-1]; for (int j = target; j >= 0; j--) { // 不选该物品 boolean no = f[j]; // 选该物品 boolean yes = j >= t ? f[j-t] : false; f[j] = no | yes; } } return f[target]; } } 复制代码
- 时间复杂度：targettargettarget 为数组总和的一半，nnn 数组元素个数。为共有 n∗targetn * targetn∗target 个状态需要被转移，复杂度为 O(n∗target)O(n * target)O(n∗target)
- 空间复杂度：O(target)O(target)O(target)
总结
今天我们又做了一遍「416. 分割等和子集」，但却是以另外一个角度进行求解：
通过修改 01 背包的「状态定义」和「转移方程」实现「直接求解」。
但这样的做法属于特题特解吗？
其实不属于。反而这是「背包问题」中一个可推广的性质：
我们可以通过将一个背包问题的「状态定义」从最多不超过 XX 容量修改为背包容量恰好为 XX，同时再把「有效值构造」出来，也即是将物品下标调整为从 1 开始，设置 dp[0][0]dp[0][0]dp[0][0] 为初始值。
这其实是另外一类「背包问题」，它不对应「价值最大化」，对应的是「能否取得最大/特定价值」。这样的「背包问题」同样具有普遍性。
需要大家进行掌握 ~
背包问题（目录）
- 01背包 : 背包问题 第一讲
- 【练习】01背包 : 背包问题 第二讲
- 【学习&练习】01背包 : 本篇
- 完全背包 : 背包问题 第四讲
- 多重背包 : 背包问题 第八讲
- 多重背包（优化篇）
- 【练习】分组背包 : 背包问题 第十三讲
- 多维背包
- 树形背包 : 背包问题 第十六讲
- 【练习篇】树形背包 : 背包问题 第十七讲
- 【练习篇】树形背包
- 背包求方案数
- 【练习】背包求方案数
- 背包求具体方案
- 【练习】背包求具体方案
- 泛化背包
- 【练习】泛化背包
