背包问题概述
背包问题 (Knapsack problem) 是⼀种组合优化的
NP完全问题
。
问题可以描述为：给定⼀组物品，每种物品都有⾃⼰的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最⾼。
根据物品的个数，分为如下⼏类：
•
01 背包问题：每个物品只有⼀个
•
完全背包问题：每个物品有⽆限多个
•
多重背包问题：每件物品最多有 si 个
•
混合背包问题：每个物品会有上⾯三种情况......
•
分组背包问题：物品有 n 组，每组物品⾥有若⼲个，每组⾥最多选⼀个物品
其中上述分类⾥⾯，根据背包是否装满，⼜分为两类：
•
不⼀定装满背包
•
背包⼀定装满
优化⽅案：
•
空间优化 - 滚动数组
•
单调队列优化
•
贪⼼优化
根据限定条件的个数，⼜分为两类：
•
限定条件只有⼀个：⽐如体积 -> 普通的背包问题
•
限定条件有两个：⽐如体积 + 重量 -> ⼆维费⽤背包问题
根据不同的问法，⼜分为很多类：
•
输出⽅案
•
求⽅案总数
•
最优⽅案
•
⽅案可⾏性
其实还有很多分类，但是我们仅需了解即可。因此，背包问题种类⾮常繁多，题型⾮常丰富，难度也是⾮常难以捉摸。但是，尽管种类⾮常多，都是从 01 背包问题演化过来的。所以，⼀定要把 01 背包问题学好。
01 背包问题
例题一
解法（动态规划）：
算法思路：
背包问题的状态表⽰⾮常经典，如果⼤家不知道怎么来的，就把它当成⼀个「模板」记住吧~
我们先解决第⼀问：
1.
状态表⽰：
dp[i][j]
表⽰：从前
i
个物品中挑选，总体积「不超过」
j
，所有的选法中，能挑选出来的最⼤价值。
2.
状态转移⽅程：
线性
dp
状态转移⽅程分析⽅式，⼀般都是根据「最后⼀步」的状况，来分情况讨论：
i.
不选第
i
个物品：相当于就是去前
i - 1
个物品中挑选，并且总体积不超过
j
。此时 dp[i][j] = dp[i - 1][j]
；
ii.
选择第
i
个物品：那么我就只能去前
i - 1
个物品中，挑选总体积不超过
j - v[i]的物品。此时 dp[i][j] = dp[i - 1][j - v[i]] + w[i]
。但是这种状态不⼀定存在，因此需要特判⼀下。
综上，状态转移⽅程为：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) 。
3.
初始化：
我们多加⼀⾏，⽅便我们的初始化，此时仅需将第⼀⾏初始化为
0
即可。因为什么也不选，也能满⾜体积不⼩于 j
的情况，此时的价值为
0
。
4.
填表顺序：
根据「状态转移⽅程」，我们仅需「从上往下」填表即可。
5.
返回值：
根据「状态表⽰」，返回
dp[n][V]
。
接下来解决第⼆问：
第⼆问仅需微调⼀下
dp
过程的五步即可。
因为有可能凑不⻬
j
体积的物品，因此我们把不合法的状态设置为
-1
。
1.
状态表⽰：
dp[i][j]
表⽰：从前
i
个物品中挑选，总体积「正好」等于
j
，所有的选法中，能挑选出来的最⼤价值。
2.
状态转移⽅程：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])
。 但是在使⽤ dp[i - 1][j - v[i]]
的时候，不仅要判断
j >= v[i]
，⼜要判断
dp[i - 1][j - v[i]] 表⽰的情况是否存在，也就是
dp[i - 1][j - v[i]] != -1
。
3.
初始化：
我们多加⼀⾏，⽅便我们的初始化：
i.
第⼀个格⼦为
0
，因为正好能凑⻬体积为
0
的背包；
ii.
但是第⼀⾏后⾯的格⼦都是
-1
，因为没有物品，⽆法满⾜体积⼤于
0
的情况。
4.
填表顺序：
根据「状态转移⽅程」，我们仅需「从上往下」填表即可。
5.
返回值：
由于最后可能凑不成体积为
V
的情况，因此返回之前需要「特判」⼀下。
空间优化：
背包问题基本上都是利⽤「滚动数组」来做空间上的优化：
i.
利⽤「滚动数组」优化；
ii.
直接在「原始代码」上修改。
在01背包问题中，优化的结果为：
i.
删掉所有的横坐标；
ii.
修改⼀下
j
的遍历顺序。
例题二
解法（动态规划）：
算法思路：
先将问题转化成我们「熟悉」的题型。如果数组能够被分成两个相同元素之和相同的⼦集，那么原数组必须有下⾯⼏个性质：
i.
所有元素之和应该是⼀个偶数；
ii.
数组中最⼤的元素应该⼩于所有元素总和的⼀半；
iii.
挑选⼀些数，这些数的总和应该等于数组总和的⼀半。
根据前两个性质，我们可以提前判断数组能够被划分。根据最后⼀个性质，我们发现问题就转化成
了「01 背包」的模型：
i.
数组中的元素只能选择⼀次；
ii.
每个元素⾯临被选择或者不被选择的处境；
iii.
选出来的元素总和要等于所有元素总和的⼀半。
其中，数组内的元素就是物品，总和就是背包。那么我们就可以⽤背包模型的分析⽅式，来处理这道题。
请⼤家注意，「不要背」状态转移⽅程，因为题型变化之后，状态转移⽅程就会跟着变化。我们要记住的是分析问题的模式。⽤这种分析问题的模式来解决问题。
1.
状态表⽰：
dp[i][j]
表⽰在前
i
个元素中选择，所有的选法中，能否凑成总和为
j
这个数。
2.
状态转移⽅程：
⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，分情况讨论：
i.
不选择
nums[i]
：那么我们是否能够凑成总和为
j
，就要看在前
i - 1
个元素中选，能否凑成总和为 j
。根据状态表⽰，此时
dp[i][j] = dp[i - 1][j]
；
ii.
选择
nums[i]
：这种情况下是有前提条件的，此时的
nums[i]
应该是⼩于等于
j
。
因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们是否能够凑成总和为 j
，就要看在前
i - 1
个元素中选，能否凑成总和为
j - nums[i]
。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j - nums[i]]
。
综上所述，两种情况下只要有⼀种能够凑成总和为
j
，那么这个状态就是
true
。因此，状态转移⽅程为： dp[i][j] = dp[i - 1][j]
if(nums[i - 1] <= j) dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i-1]]
3.
初始化：
由于需要⽤到上⼀⾏的数据，因此我们可以先把第⼀⾏初始化。第⼀⾏表⽰不选择任何元素，要凑成⽬标和 j
。只有当⽬标和为
0
的时候才能做到，因此第⼀⾏仅需初始化第⼀个元素 dp[0][0] = true
4.
填表顺序：
根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。
5.
返回值：
根据「状态表⽰」，返回
dp[n][aim]
的值。其中 n
表⽰数组的⼤⼩，
aim
表⽰要凑的⽬标和。
6.
空间优化：
所有的「背包问题」，都可以进⾏空间上的优化。
对于 01背包类型的，我们的优化策略是：
i.
删掉第⼀维；
ii.
修改第⼆层循环的遍历顺序即可。
例题三
解法（动态规划）：
算法思路：
本题可以直接⽤「暴搜」的⽅法解决。但是稍微⽤数学知识分析⼀下，就能转化成我们常⻅的「背
包模型」的问题。设我们最终选取的结果中，前⾯加 + 号的数字之和为 a
，前⾯加 - 号的数字之和为
b
，整个数组的总和为 sum
，于是我们有：
▪
a + b = sum
▪
a - b = target
上⾯两个式⼦消去
b
之后，可以得到
a = (sum + target) / 2，也就是说，我们仅需在 nums
数组中选择⼀些数，将它们凑成和为
(sum + target) / 2
即可。问题就变成了
416. 分割等和⼦集
这道题。
我们可以⽤相同的分析模式，来处理这道题。
1.
状态表⽰：
dp[i][j]
表⽰：在前
i
个数中选，总和正好等于
j
，⼀共有多少种选法。
2.
状态转移⽅程：
⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，我们有「选择」最后⼀个元素或者「不
选择」最后⼀个元素两种策略：
i.
不选
nums[i]
：那么我们凑成总和
j
的总⽅案，就要看在前
i - 1
个元素中选，凑成总和为 j
的⽅案数。根据状态表⽰，此时
dp[i][j] = dp[i - 1][j]
；
ii.
选择
nums[i]
：这种情况下是有前提条件的，此时的
nums[i]
应该是⼩于等于
j
。
因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们能够凑成总和为 j 的⽅案数，就要看在前
i - 1
个元素中选，能否凑成总和为
j - nums[i]
。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j - nums[i]]
综上所述，两种情况如果存在的话，应该要累加在⼀起。因此，状态转移⽅程为：
dp[i][j] = dp[i - 1][j]
if(nums[i - 1] <= j) dp[i][j] = dp[i][j] += dp[i - 1][j - nums[i - 1]]
3.
初始化：
由于需要⽤到「上⼀⾏」的数据，因此我们可以先把第⼀⾏初始化。第⼀⾏表⽰不选择任何元素，要凑成⽬标和 j
。只有当⽬标和为
0
的时候才能做到，因此第⼀⾏仅需初始化第⼀个元素 dp[0][0] = 1
4.
填表顺序：
根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。
5.
返回值：
根据「状态表⽰」，返回
dp[n][aim]
的值。其中 n
表⽰数组的⼤⼩，
aim
表⽰要凑的⽬标和。
6.
空间优化：
所有的「背包问题」，都可以进⾏空间上的优化。
对于 01背包类型的，我们的优化策略是：
i.
删掉第⼀维；
ii.
修改第⼆层循环的遍历顺序即可。
例题四
解法（动态规划）：
算法思路：
先将问题「转化」成我们熟悉的题型。
▪
任意两块⽯头在⼀起粉碎，重量相同的部分会被丢掉，重量有差异的部分会被留下来。那就相当于在原始的数据的前⾯，加上「加号」或者「减号」，是最终的结果最⼩即可。也就是说把原始的⽯头分成两部分，两部分的和越接近越好。
▪
⼜因为当所有元素的和固定时，分成的两部分越接近数组「总和的⼀半」，两者的差越⼩。
因此问题就变成了：在数组中选择⼀些数，让这些数的和尽量接近
sum / 2
，如果把数看成物品，每个数的值看成体积和价值，问题就变成了「01 背包问题」。
1.
状态表⽰：
dp[i][j]
表⽰在前
i
个元素中选择，总和不超过 j，此时所有元素的「最⼤和」。
2.
状态转移⽅程：
⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，分情况讨论：
i.
不选
stones[i]
：那么我们是否能够凑成总和为
j
，就要看在前
i - 1
个元素中选，能否凑成总和为 j
。根据状态表⽰，此时
dp[i][j] = dp[i - 1][j]
；
ii.
选择
stones[i]
：这种情况下是有前提条件的，此时的
stones[i]
应该是⼩于等于 j 。因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们是否能够凑成总和为 j
，就要看在前
i - 1
个元素中选，能否凑成总和为
j - stones[i]
。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j -stones[i]] + stones[i]
。
综上所述，我们要的是最⼤价值。因此，状态转移⽅程为：
dp[i][j] = dp[i - 1][j]
if(j >= stones[i]) dp[i][j] = max(dp[i][j] ， dp[i - 1][j - stones[i]] + stones[i]) 。
3.
初始化：
由于需要⽤到上⼀⾏的数据，因此我们可以先把第⼀⾏初始化。第⼀⾏表⽰「没有⽯⼦」。因此想凑成⽬标和 j
，最⼤和都是
0
。
4.
填表顺序：
根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。
5.
返回值：
a.
根据「状态表⽰」，先找到最接近
sum / 2
的最⼤和
dp[n][sum / 2]
；
b.
因为我们要的是两堆⽯⼦的差，因此返回
sum - 2 * dp[n][sum / 2]
。
6.
空间优化：
所有的背包问题，都可以进⾏「空间」上的优化。
对于 01背包类型的，我们的优化策略是：
i.
删掉第⼀维；
ii.
修改第⼆层循环的「遍历顺序」即可。
完全背包问题
例题一
解法（动态规划）：
算法思路：
背包问题的状态表⽰⾮常经典，如果⼤家不知道怎么来的，就把它当成⼀个模板记住吧~
我们先解决第⼀问：
1.
状态表⽰：
dp[i][j]
表⽰：从前
i
个物品中挑选，总体积不超过
j
，所有的选法中，能挑选出来的最⼤价值.（这⾥是和 01背包⼀样哒）
2.
状态转移⽅程：
线性
dp
状态转移⽅程分析⽅式，⼀般都是根据最后⼀步的状况，来分情况讨论。但是最后⼀个物品能选很多个，因此我们的需要分很多情况：
i.
选
0
个第
i
个物品：此时相当于就是去前
i - 1
个物品中挑选，总体积不超过
j
。此时最⼤价值为 dp[i - 1][j]
；
ii.
选
1
个第
i
个物品：此时相当于就是去前
i - 1
个物品中挑选，总体积不超过
j - v[i] 。因为挑选了⼀个
i
物品，此时最⼤价值为 dp[i - 1][j - v[i]] + w[i]
；
iii.
选 2 个第 i
个物品：此时相当于就是去前
i - 1
个物品中挑选，总体积不超过
j - 2 * v[i] 。因为挑选了两个
i
物品，此时最⼤价值为
dp[i - 1][j - 2 * v[i]] + 2 * w[i] ；
iv.
......
综上，我们的状态转移⽅程为：
dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i], dp[i-1][j- 2*v[i]]+2*w[i]...)
当我们发现，计算⼀个状态的时候，需要⼀个循环才能搞定的时候，我们要想到去优化。优化的⽅
向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态，通常就是⽤数学的⽅式做⼀下等价替换。我们发
现第⼆维是有规律的变化的，因此我们去看看
dp[i][j - v[i]]
这个状态：
dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2*v[i]]+w[i],dp[i-1] [j-3*v[i]]+2*w[i]...)
我们发现，把
dp[i][j - v[i]]
加上
w[i]
正好和
dp[i][j]
中除了第⼀项以外的全部⼀致，因此我们可以修改我们的状态转移⽅程为： dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]) 。
3.
初始化：
我们多加⼀⾏，⽅便我们的初始化，此时仅需将第⼀⾏初始化为
0
即可。因为什么也不选，也能 满⾜体积不⼩于 j
的情况，此时的价值为
0
。
4.
填表顺序：
根据状态转移⽅程，我们仅需从上往下填表即可。
5.
返回值：
根据状态表⽰，返回
dp[n][V]
。
接下来解决第⼆问：
第⼆问仅需微调⼀下
dp
过程的五步即可。因为有可能凑不⻬ j
体积的物品，因此我们把不合法的状态设置为
-1
。
1.
状态表⽰：
dp[i][j]
表⽰：从前
i
个物品中挑选，总体积正好等于
j
，所有的选法中，能挑选出来的最⼤价值。
2.
状态转移⽅程：
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
。
但是在使⽤
dp[i][j - v[i]]
的时候，不仅要判断
j >= v[i]
，⼜要判断
dp[i][j - v[i]] 表⽰的情况是否存在，也就是
dp[i][j - v[i]] != -1
。
3.
初始化：
我们多加⼀⾏，⽅便我们的初始化：
i.
第⼀个格⼦为
0
，因为正好能凑⻬体积为
0
的背包；
ii.
但是第⼀⾏后⾯的格⼦都是
-1
，因为没有物品，⽆法满⾜体积⼤于
0
的情况。
4.
填表顺序：
根据状态转移⽅程，我们仅需从上往下填表即可。
5.
返回值：
由于最后可能凑不成体积为
V
的情况，因此返回之前需要特判⼀下。
空间优化：
背包问题基本上都是利⽤滚动数组来做空间上的优化：
i.
利⽤滚动数组优化；
ii.
直接在原始代码上修改。
在完全背包问题中，优化的结果为：
i.
仅需删掉所有的横坐标。
例题二
解法（动态规划）：
算法思路：
先将问题「转化」成我们熟悉的题型。
i.
在⼀些物品中「挑选」⼀些出来，然后在满⾜某个「限定条件」下，解决⼀些问题，⼤概率是「背包」模型；
ii.
由于每⼀个物品都是⽆限多个的，因此是⼀个「完全背包」问题。
接下来的分析就是基于「完全背包」的⽅式来的。
1.
状态表⽰：
dp[i][j]
表⽰：从前
i
个硬币中挑选，总和正好等于
j
，所有的选法中，最少的硬币个数。
2.
状态转移⽅程：
线性
dp
状态转移⽅程分析⽅式，⼀般都是根据「最后⼀步」的状况，来分情况讨论。但是最后⼀个物品能选很多个，因此我们的需要分很多情况：
i.
选
0
个第
i
个硬币：此时相当于就是去前
i - 1
个硬币中挑选，总和正好等于
j
。此时最少的硬币个数为 dp[i - 1][j]
；
ii.
选
1
个第
i
个硬币：此时相当于就是去前
i - 1
个硬币中挑选，总和正好等于
j - v[i] 。因为挑选了⼀个
i
硬币，此时最少的硬币个数为
dp[i - 1][j - coins[i]] + 1 ；
iii.
选
2
个第
i
个硬币：此时相当于就是去前
i - 1
个硬币中挑选，总和正好等于
j - 2 * coins 。因为挑选了两个
i
硬币，此时最少的硬币个数为
dp[i - 1][j - 2 * coins[i]] + 2 ；
iv.
......
结合我们在完全背包⾥⾯的优化思路，我们最终得到的状态转移⽅程为：
dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1)
。
这⾥教给⼤家⼀个技巧，就是相当于把第⼆种情况
dp[i - 1][j - coins[i]] + 1
⾥⾯的 i - 1
变成
i
即可。
3.
初始化：
初始化第⼀⾏即可。这⾥因为取 min
，所以我们可以把⽆效的地⽅设置成⽆穷⼤
(0x3f3f3f3f)
因为这⾥要求正好凑成总和为
j
，因此，需要把第⼀⾏除了第⼀个位置的元素，都设置成⽆穷⼤。
4.
填表顺序：
根据「状态转移⽅程」，我们仅需「从上往下」填表即可。
5.
返回值：
根据「状态表⽰」，返回
dp[n][V]
。但是要特判⼀下，因为有可能凑不到。
空间优化后的算法代码：
例题三
解法（动态规划）：
算法思路：
先将问题「转化」成我们熟悉的题型。
i.
在⼀些物品中「挑选」⼀些出来，然后在满⾜某个「限定条件」下，解决⼀些问题，⼤概率是背包模型；
ii.
由于每⼀个物品都是⽆限多个的，因此是⼀个「完全背包」问题。接下来的分析就是基于「完全背包」的⽅式来的。
1.
状态表⽰：
dp[i][j]
表⽰：从前
i
个硬币中挑选，总和正好等于
j
，⼀共有多少种选法。
2.
状态转移⽅程：
线性
dp
状态转移⽅程分析⽅式，⼀般都是「根据最后⼀步」的状况，来分情况讨论。但是最后⼀个物品能选很多个，因此我们的需要分很多情况：
i.
选
0
个第
i
个硬币：此时相当于就是去前
i - 1
个硬币中挑选，总和正好等于
j
。此时选法个数为 dp[i - 1][j]
；
ii.
选
1
个第
i
个硬币：此时相当于就是去前
i - 1
个硬币中挑选，总和正好等于
j - v[i] 。因为挑选了⼀个
i 硬币，此时选法个数为 dp[i - 1][j - coins[i]] ；
iii.
选
2
个第
i
个硬币：此时相当于就是去前
i - 1
个硬币中挑选，总和正好等于
j - 2 * coins 。因为挑选了两个
i 硬币，此时选法个数为 dp[i - 1][j - 2 * coins[i]] ；
iv.
......
结合我们在完全背包⾥⾯的「优化思路」，我们最终得到的状态转移⽅程为：
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]
。
3.
初始化：
初始化第⼀⾏即可。
第⼀⾏表⽰没有物品，没有物品正好能凑能和为
0
的情况。因此
dp[0][0] = 1
，其余位置都是 0
种情况。
4.
填表顺序：
根据「状态转移⽅程」，我们仅需「从上往下」填表即可。
5.
返回值：
根据「状态表⽰」，返回
dp[n][V]
。
空间优化后的算法代码：
例题四
解法（动态规划）：
算法思路：
这⾥给出⼀个⽤「拆分出相同⼦问题」的⽅式，定义⼀个状态表⽰。（⽤「完全背包」⽅式的解法
就仿照之前的分析模式就好啦~~）为了叙述⽅便，把和为 n
的完全平⽅数的最少数量简称为「最⼩数量」。对于 12
这个数，我们分析⼀下如何求它的最⼩数量。
▪
如果
12
本⾝就是完全平⽅数，我们不⽤算了，直接返回
1
；
▪
但是
12
不是完全平⽅数，我们试着把问题分解⼀下：
1.
情况⼀：拆出来⼀个
1
，然后看看
11
的最⼩数量，记为
x1
；
2.
情况⼆：拆出来⼀个
4
，然后看看
8
的最⼩数量，记为
x2
；（为什么拆出来
4
，⽽不拆出来 2
呢？）
3.
情况三：拆出来⼀个
8
......
其中，我们接下来求
11
、
8
的时候，其实⼜回到了原来的问题上。因此，我们可以尝试⽤ dp
的策略，将
1 2 3 4 6
等等这些数的最⼩数量依次保存起来。再求较⼤的 n
的时候，直接查表，然后找出最⼩数量。
1.
状态表⽰：
dp[i]
表⽰：和为
i
的完全平⽅数的最少数量。
2.
状态转移⽅程：
对于
dp[i]
，根据思路那⾥的分析我们知道，可以根据⼩于等于
i
的所有完全平⽅数
x
进⾏划分：
▪
x = 1
时，最⼩数量为：
1 + dp[i - 1]
；
▪
x = 4
时，最⼩数量为：
1 + dp[i - 4]
......
⼀直枚举到
x <= i
为⽌。
为了⽅便枚举完全平⽅数，我们采⽤下⾯的策略：
for(int j = 1; j * j <= i; j++)
综上所述，状态转移⽅程为： dp[i] = min(dp[i], dp[i - j * j] + 1)
3.
初始化：
当
n = 0
的时候，没法拆分，结果为
0
； 当 n = 1
的时候，显然为
1
。
4.
填表顺序：
从左往右。
5.
返回值：
根据题意，返回
dp[n]
的值。
空间优化后的算法代码：
⼆维费⽤的背包问题
例题一
解法（动态规划）：
算法思路：
先将问题转化成我们熟悉的题型。
i.
在⼀些物品中「挑选」⼀些出来，然后在满⾜某个「限定条件」下，解决⼀些问题，⼤概率是背包模型；
ii.
由于每⼀个物品都只有
1
个，因此是⼀个「01 背包问题」。
但是，我们发现这⼀道题⾥⾯有「两个限制条件」。因此是⼀个「⼆维费⽤的 01 背包问题」。那
么我们定义状态表⽰的时候，来⼀个三维
dp
表，把第⼆个限制条件加上即可。
1.
状态表⽰：
dp[i][j][k]
表⽰：从前
i
个字符串中挑选，字符
0
的个数不超过
j
，字符
1
的个数不超过 k
，所有的选法中，最⼤的⻓度。
2.
状态转移⽅程：
线性
dp
状态转移⽅程分析⽅式，⼀般都是「根据最后⼀步」的状况，来分情况讨论。为了⽅便叙述，我们记第 i
个字符中，字符
0
的个数为
a
，字符
1
的个数为
b
：
i.
不选第
i
个字符串：相当于就是去前
i - 1
个字符串中挑选，并且字符
0
的个数不超过 j
，字符
1
的个数不超过
k
。此时的最⼤⻓度为
dp[i][j][k] = dp[i - 1] [j][k] ；
ii.
选择第
i
个字符串：那么接下来我仅需在前
i - 1
个字符串⾥⾯，挑选出来字符
0
的个数不超过 j - a
，字符
1
的个数不超过
k - b
的最⻓⻓度，然后在这个⻓度后⾯加上字符串 i
即可。此时
dp[i][j][k] = dp[i - 1][j - a][k - b] + 1
。 但是这种状态不⼀定存在，因此需要特判⼀下。
综上，状态转移⽅程为：
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a] [k - b] + 1) 。
3.
初始化：
当没有字符串的时候，没有⻓度，因此初始化为
0
即可。
4.
填表顺序：
保证第⼀维的循环「从⼩到⼤」即可。
5.
返回值：
根据「状态表⽰」，我们返回
dp[len][m][n]
。 其中 len
表⽰字符串数组的⻓度。
6.
空间优化：
所有的「背包问题」，都可以进⾏空间上的优化。
对于「⼆维费⽤的 01 背包」类型的，我们的优化策略是：
i.
删掉第⼀维；
ii.
修改第⼆层以及第三层循环的遍历顺序即可。
例题二
解法（动态规划）：
算法思路：
这道题⽬⾮常难读懂，但是如果结合例⼦多读⼏遍，你就会发现是⼀个经典的「⼆维费⽤的背包问 题」。因此我们可以仿照「⼆维费⽤的背包」来定义状态表⽰。
1.
状态表⽰：
dp[i][j][k]
表⽰：从前
i
个计划中挑选，总⼈数不超过
j
，总利润⾄少为
k
，⼀共有多少种选法。
注意注意注意，这道题⾥⾯出现了⼀个「⾄少」，和我们之前做过的背包问题不⼀样。因此，我们 在分析「状态转移⽅程」的时候要结合实际情况考虑⼀下。
2.
状态转移⽅程：
⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，我们有「选择」最后⼀个元素或者「不
选择」最后⼀个元素两种策略：
i.
不选
i
位置的计划：那我们只能去前
i - 1
个计划中挑选，总⼈数不超过
j
，总利润⾄少为 k
。此时⼀共有
dp[i - 1][j][k]
种选法；
ii.
选择
i
位置的计划：那我们在前
i - 1
个计划中挑选的时候，限制就变成了，总⼈数不超过 j - g[i]
，总利润⾄少为
k - p[i]
。此时⼀共有
dp[i - 1][j - g[i]][k - p[i]] 。
第⼆种情况下有两个细节需要注意：
1.
j - g[i] < 0
：此时说明
g[i]
过⼤，也就是⼈数过多。因为我们的状态表⽰要求⼈数是不能超过 j
的，因此这个状态是不合法的，需要舍去。
2.
k - p[i] < 0
：此时说明
p[i]
过⼤，也就是利润太⾼。但是利润⾼，不正是我们想要的嘛？所以这个状态「不能舍去」。但是问题来了，我们的 dp
表是没有负数的下标的，这就意味着这些状态我们⽆法表⽰。其实，根本不需要负的下标，我们根据实际情况来看，如果这个任务的利润已经能够达标了，我们仅需在之前的任务中，挑选出来的利润⾄少为 0
就可以了。因为实际情况不允许我们是负利润，那么负利润就等价于利润⾄少为 0
的情况。所以说这种情况就等价于
dp[i][j][0]
，我们可以对
k - p[i] 的结果与
0
取⼀个
max
。
综上，我们的状态转移⽅程为： dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - g[i - 1]][max(0, k - p[i - 1])] 。
3.
初始化：
当我们的利润为 0 的时候，我们的利润为 0 ，此时⽆论⼈数限制为多少，我们都能找到⼀个「空集」的 ⽅案。因此初始化 dp[i][j][0]
的位置为
1 ，其中0 <= i <= m,0 <= j <= n 。
4.
填表顺序：
根据「状态转移⽅程」，我们保证
i
从⼩到⼤即可。
5.
返回值：
根据「状态表⽰」，我们返回
dp[len][m][n]
。
其中
len
表⽰字符串数组的⻓度。
6.
空间优化：
所有的「背包问题」，都可以进⾏空间上的优化。
对于「⼆维费⽤的 01 背包」类型的，我们的优化策略是：
i.
删掉第⼀维；
ii.
修改第⼆层以及第三层循环的遍历顺序即可。
似包⾮包
例题一
解法（动态规划）：
算法思路：
⼀定要注意，我们的背包问题本质上求的是「组合」数问题，⽽这⼀道题求的是「排列数」问题。 因此我们不能被这道题给迷惑，还是⽤常规的 dp
思想来解决这道题。
1.
状态表⽰：
这道题的状态表⽰就是根据「拆分出相同⼦问题」的⽅式，抽象出来⼀个状态表⽰：当我们在求 target
这个数⼀共有⼏种排列⽅式的时候，对于最后⼀个位置，如果我们拿出数组中的⼀个数 x
，接下来就是去找
target - x
⼀共有多少种排列⽅式。因此我们可以抽象出来⼀个状态表⽰：
dp[i]
表⽰：总和为
i
的时候，⼀共有多少种排列⽅案。
2.
状态转移⽅程：
对于
dp[i]
，我们根据「最后⼀个位置」划分，我们可以选择数组中的任意⼀个数nums[j] ，其中
0 <= j <= n - 1
。 当 nums[j] <= target
的时候，此时的排列数等于我们先找到
target - nums[j]
的⽅
案数，然后在每⼀个⽅案后⾯加上⼀个数字
nums[j]
即可。因为有很多个 j
符合情况，因此我们的状态转移⽅程为：
dp[i] += dp[target - nums[j] ，其中
0 <= j <= n - 1
。
3.
初始化：
当和为
0
的时候，我们可以什么都不选，「空集」⼀种⽅案，因此
dp[0] = 1
。
4.
填表顺序：
根据「状态转移⽅程」易得「从左往右」。
5.
返回值：
根据「状态表⽰」，我们要返回的是
dp[target]
的值。
卡特兰数
例题一
解法（动态规划）：
算法思路：
这道题属于「卡特兰数」的⼀个应⽤，同样能解决的问题还有「合法的进出栈序列」、「括号匹配
的括号序列」、「电影购票」等等。如果感兴趣的同学可以「百度」搜索卡特兰数，会有很多详细
的介绍。
1.
状态表⽰：
这道题的状态表⽰就是根据「拆分出相同⼦问题」的⽅式，抽象出来⼀个状态表⽰：
当我们在求个数为
n
的
BST
的个数的时候，当确定⼀个根节点之后，左右⼦树的结点「个数」也确定了。此时左右⼦树就会变成相同的⼦问题，因此我们可以这样定义状态表⽰：dp[i] 表⽰：当结点的数量为
i
个的时候，⼀共有多少颗
BST
。难的是如何推导状态转移⽅程，因为它跟我们之前常⻅的状态转移⽅程不是很像。
2.
状态转移⽅程：
对于
dp[i]
，此时我们已经有
i
个结点了，为了⽅便叙述，我们将这 i 个结点排好序，并且编上 1, 2, 3, 4, 5.....i
的编号。那么，对于所有不同的 BST
，我们可以按照下⾯的划分规则，分成不同的
i
类：「按照不同的头结点来分类」。分类结果就是：
i.
头结点为
1
号结点的所有
BST
ii.
头结点为
2
号结点的所有
BST
iii.
......
如果我们能求出「每⼀类中的
BST
的数量」，将所有类的
BST
数量累加在⼀起，就是最后结果。 接下来选择「头结点为 j
号」的结点，来分析这
i
类
BST
的通⽤求法。如果选择「 j
号结点来作为头结点」，根据
BST
的定义：
i.
j 号结点的「左⼦树」的结点编号应该在
[1, j - 1]
之间，⼀共有
j - 1
个结点。那么 j
号结点作为头结点的话，它的「左⼦树的种类」就有
dp[j - 1]
种（回顾⼀下我们 dp
数组的定义哈）；
ii.
j 号结点的「右⼦树」的结点编号应该在
[j + 1, i]
之间，⼀共有
i - j
个结点。那么 j
号结点作为头结点的话，它的「右⼦树的种类」就有
dp[i - j]
种；根据「排列组合」的原理可得： j
号结点作为头结点的
BST
的种类⼀共有
dp[j - 1] * dp[i - j] 种！因此，我们只要把「不同头结点的 BST
数量」累加在⼀起，就能得到
dp[i]
的值：
dp[i] += dp[j - 1] * dp[i - j] ( 1 <= j <= i) 。「注意⽤的是
+=
，并且
j
从
1
变化到 i
」。
3.
初始化：
我们注意到，每⼀个状态转移⾥⾯的
j - 1
和
i - j
都是⼩于
i
的，并且可能会⽤到前⼀个的状态（当 i = 1
，
j = 1
的时候，要⽤到
dp[0]
的数据）。因此要先把第⼀个元素初始化。当 i = 0
的时候，表⽰⼀颗空树，「空树也是⼀颗⼆叉搜索树」，因此
dp[0] = 1
。
4.
填表顺序：
根据「状态转移⽅程」，易得「从左往右」。
5.
返回值：
根据「状态表⽰」，我们要返回的是
dp[n]
的值。
