动态规划算法:背包问题

背包问题概述

背包问题 (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] 的值。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/671908.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vector实现后半部分

一.迭代器失效 1.定义 指原迭代器在扩容/缩容/修改后指向无效元素或无效地址处 erase的迭代器失效 2.原因&#xff1a; 1.有的编译器实现erase会缩容拷贝 2.删除最后一个后&#xff0c;其指向无效元素 VS中不允许再次使用erase完的迭代器&#xff0c;为了让编写的代码移植…

32位与64位程序下函数调用的异同——计科学习中缺失的内容

前言 今天&#xff0c;通过一个有趣的案例&#xff0c;从反编译的角度看一下C语言中函数参数是如何传递的。 创建main.c文件&#xff0c;将下面实验代码拷贝到main.c文件中。 # main.c #include <stdio.h>int test(int a, int b, int c, int d, int e, int f, int g, …

浔川python社获得全网博主原力月度排名泸州地区第二名!

今日&#xff0c;浔川python社在查看全网博主原力月度排名泸州地区时&#xff0c;一看就震惊啦&#xff01; 全网博主原力月度排名泸州地区排名榜单 全网博主原力月度排名泸州地区第二名为&#xff1a;浔川python社。 感谢粉丝们的支持&#xff01;浔川python社还会继续努力&a…

ubuntu--Linux使用

Linux使用 Linux 系统简介 linux Linux 就是一个操作系统&#xff0c;与 Windows 和 Mac OS 一样是操作系统 。 操作系统在整个计算机系统中的角色 : Linux 主要是 系统调用 和 内核 那两层。使用的操作系统还包含一些在其上运行的应用程序&#xff0c;比如vim、google、vs…

Glow模型【图解版加代码】

论文&#xff1a;Glow: Generative Flow with Invertible 1x1 Convolutions 代码&#xff1a;pytorch版本&#xff1a;rosinality/glow-pytorch: PyTorch implementation of Glow (github.com) 正版是TensorFlow版本 openai的 参考csdn文章&#xff1a;Glow-pytorch复现gith…

spoon工具的常用基础操作

一些常用转换工具 1、emp表输入->excel表输出 emp表输入&#xff0c;可以进行预览查看数据有没有过来excel表输出 成功执行后&#xff0c;可以到保存的excel位置进行查看。 2、excel输入->表输出 运行转换后可以在oracle进行查看是否有成功创建这个表 3、对部门最高…

十_信号11 - 函数sigsetjmp() 和 siglongjmp()

也就是说&#xff0c;正常情况下&#xff0c;当捕捉到一个信号&#xff0c;并调用该信号的信号处理程序时&#xff0c;被捕捉的信号会被加入到当前进程的信号屏蔽字中&#xff0c;以防止在本次信号处理程序还没有完成的时候&#xff0c;再次触发该信号&#xff0c; 发生重入。 …

罕见!史诗级“大堵船”

新加坡港口的停泊延误时间已延长至7天&#xff0c;积压的集装箱数量达到惊人的450000标准箱&#xff0c;远超新冠疫情暴发时期的数轮高点。业内认为&#xff0c;近期东南亚恶劣的天气情况加剧了该区域港口拥堵。 5月31日&#xff0c;上海航运交易所&#xff08;下称“航交所”…

针对硅基氮化镓高电子迁移率晶体管(GaN-HEMT)的准物理等效电路模型,包含基板中射频漏电流的温度依赖性

来源&#xff1a;Quasi-Physical Equivalent Circuit Model of RF Leakage Current in Substrate Including Temperature Dependence for GaN-HEMT on Si&#xff08;TMTT 23年&#xff09; 摘要 该文章提出了一种针对硅基氮化镓高电子迁移率晶体管&#xff08;GaN-HEMT&…

【算法】理解堆排序

堆排序&#xff0c;无疑与堆这种数据结构有关。在了解堆排序之前&#xff0c;我们需要先了解堆的建立与维护方法。 堆 堆&#xff08;二插堆&#xff09;可以用一种近似的完全二叉树来表示&#xff0c;该二叉树除了叶子结点之外&#xff0c;其余节点均具有两个子女&#xff0c…

HCIP--RIP协议的实验 + RIP笔记

RIP实验&#xff1a; 实验思路&#xff1a; 1.规划IP&#xff0c;配置环回&#xff0c;接口IP 2.在3个路由器上跑通rip; 2.在边界路由器上用rip协议 设置缺省路由&#xff1b; [r3]rip [r3-rip-1]default-route originate 3.在r1、r2的主干接口上设置路由汇总 RIPV2手工汇…

MySQL数据库的约束

MySQL对于数据库存储的数据, 做出一些限制性要求, 就叫做数据库的"约束". 在每一列的 列名, 类型 后面加上"约束". 一. not null (非空) 指定某列不能存储null值. 二. unique (唯一) 保证这一列的每行必须有唯一值. 我们可以看到, 给 table 的 sn 列插…

Ubuntu系统配置DDNS-GO【笔记】

DDNS-GO 是一个基于 Go 语言的动态 DNS (DDNS) 客户端&#xff0c;用于自动更新你的 IP 地址到 DNS 记录上。这对于经常变更 IP 地址的用户&#xff08;如使用动态 IP 的家庭用户或者小型服务器&#xff09;非常有用。 此文档实验环境为&#xff1a;ubuntu20.04.6。 在Ubuntu…

基于Django的博客系统之登录增加忘记密码(八)

需求 描述&#xff1a; 用户忘记密码时&#xff0c;提供一种重置密码的方法&#xff0c;以便重新获得账户访问权限。规划&#xff1a; 创建一个包含邮箱输入字段的表单&#xff0c;用于接收用户的重置密码请求。用户输入注册时使用的邮箱地址&#xff0c;系统发送包含重置密码…

量产导入 | 芯片测试介绍可靠性测试

作者:桃芯科技链接:https://picture.iczhiku.com/weixin/message1583129221975.html半导体芯片的defects、Faults 芯片在制造过程中,会出现很多种不同类型的defects,比如栅氧层针孔、扩散工艺造成的各种桥接、各种预期外的高阻态、寄生电容电阻造成的延迟等等,如下面图(1)…

Spring高手之路19——Spring AOP注解指南

文章目录 1. 背景2. 基于AspectJ注解来实现AOP3. XML实现和注解实现AOP的代码对比4. AOP通知讲解5. AOP时序图 1. 背景 在现代软件开发中&#xff0c;面向切面编程&#xff08;AOP&#xff09;是一种强大的编程范式&#xff0c;允许开发者跨越应用程序的多个部分定义横切关注点…

数据隐私重塑:Web3时代的隐私保护创新

随着数字化时代的不断深入&#xff0c;数据隐私保护已经成为了人们越来越关注的焦点之一。而在这个数字化时代的新篇章中&#xff0c;Web3技术作为下一代互联网的代表&#xff0c;正在为数据隐私保护带来全新的创新和可能性。本文将深入探讨数据隐私的重要性&#xff0c;Web3时…

解锁数据宝藏:高效查找算法揭秘

代码下载链接&#xff1a;https://gitee.com/flying-wolf-loves-learning/data-structure.git 目录 一、查找的原理 1.1 查找概念 1.2 查找方法 1.3平均查找长度 1.4顺序表的查找 1.5 顺序表的查找算法及分析 1.6 折半查找算法及分析 1.7 分块查找算法及分析 1.8 总结…

很多人讲不明白HTTPS,但是我能

很多人讲不明白HTTPS&#xff0c;但是我能 今天我们用问答的形式&#xff0c;来彻底弄明白HTTPS的过程 下面的问题都是 小明和小丽两个人通信为例 可以把小明想象成服务端&#xff0c;小丽想象成客户端 1. https是做什么用的&#xff1f; 答&#xff1a;数据安全传输用的。…

数学建模 —— 聚类分析(3)

目录 一、聚类分析概述 1.1 常用聚类要素的数据处理 1.1.1 总和标准化 1.1.2 标准差标准化 1.1.3 极大值标准化 1.1.4 极差的标准化 1.2 分类 1.2.1 快速聚类法&#xff08;K-均值聚类&#xff09; 1.2.2 系统聚类法&#xff08;分层聚类法&#xff09; 二、分类统计…