第一章:动态规划复习

1. 什么是动态规划
动态规划(DP)是一种把复杂问题分解成若干个可以逐步求解的子问题的思想。
以最基本的 0/1 背包为例:有 件物品,背包容量为 ,每件物品至多选一次,求总重量不超过容量时的最大价值。直接面对全部物品,需要同时考虑许多选法,一件物品是否值得选,还取决于它能够和哪些物品搭配。
如果改成逐件考虑物品,假设前面的物品在各个容量下的最优结果已经求出,现在只加入一件物品,就只需考虑选或不选它。此前许多物品的组合问题,已经由较小问题的答案处理完毕。
动态规划的核心表达,是状态设计与转移规划。
- 状态设计决定怎样重新观察问题,明确每一个较小问题的范围、限制和要求的结果。
- 转移规划决定怎样拆分一个方案,以及怎样利用较小问题的答案求出当前问题的答案。
2. 0/1 背包:求出前 件物品在每个容量下的最优解
设第 件物品的重量为 ,价值为 ,重量和价值均为正整数。背包容量 为正整数,允许一件物品都不选。
先把“从全部 件物品中选择”缩小成“只从前 件物品中选择”。加入下一件物品时,还需要为它留出空间,因此不能只求容量 下的答案,而要同时求出不同容量限制下的答案。
定义
其中 ,。下标 限定可用物品, 是容量上限,不要求恰好用完;原问题对应 。
由第 件物品的选与不选推导转移
按第 件物品是否被选分类:
- 不选:只用前 件,容量仍为 ,得到 。
- 选:先留出容量 ,其余物品只用前 件、重量不超过 ,得到 。这一类要求 。
因此,状态转移方程为
没有物品时,任何容量上限下的最大价值都是 ,因此 。每一行只依赖上一行,按 递增计算,最终取 。时间与整表空间复杂度均为 。
为什么可以直接使用子问题的最大价值
选第 件后,其余物品只受到“来自前 件、重量不超过 ”的限制。把它们换成这个限制下的最优选法,仍能与第 件物品一起放入背包,总价值也不会减少。
任意合法方案都属于选或不选中的一类,而两类子问题的合法选法也都能组成原问题的合法方案。因此,比较这两个候选就覆盖了全部可能的最优选法。
直接枚举子集要考察 种选法;现在每个物品范围、每个容量限制下的子问题只求解一次。共有 个状态,每个状态只比较两个候选,因此计算量降为 。
手算:三件物品如何逐行得到答案
背包容量为 ,三件物品的重量、价值分别为
按物品数量逐行计算,可以得到:
| 可用物品 | 容量 | 容量 | 容量 | 容量 | 容量 | 容量 | 容量 |
|---|---|---|---|---|---|---|---|
| 没有物品 | |||||||
| 前 件 | |||||||
| 前 件 | |||||||
| 前 件 |
计算 时,不选第二件得到 ;选第二件则先为它留出容量 ,再用剩余容量 的最优结果搭配,得到 。
计算 时,选第三件会给前两件留下容量 ,得到 ;不选第三件则保留 。所以最终答案为 ,选择第一件和第三件物品。
3. 线性 DP:用结尾位置限定较小问题
对于序列问题,“前若干项中的最优答案”不一定能直接接入新元素。需要根据连接规则,进一步限定较小问题。
最大连续子段和:只延长以第 项结尾的子段
给定长度为 的整数序列 ,选择一个连续且非空的子段,求最大的元素和。
只保存前 项中的最大子段和,无法保证能接上 。例如 中,前两项的最优值 来自第一项,直接加上第三项就跳过了 ,不再连续。因此,应当固定子段的右端点,定义
以第 项结尾的子段,或者只包含 ,或者在一个以第 项结尾的非空子段后面接上 ,因此
按下标递增计算,最终取 ,因为原题没有固定右端点。时间复杂度为 ,只保留前一个状态和全局最优值时,额外空间为 。
手算:固定结尾的最优值与前若干项的最优值有什么区别
被延长的子段都以 结尾,接上同一个 后仍然连续,新增的和也相同,因此只需使用其中和最大的子段。
以 为例,另记 为前 项中的最大子段和:
| 位置 | |||||
|---|---|---|---|---|---|
| 元素 | |||||
| 必须以 结尾的 | |||||
| 前 项中的最优值 |
计算第三项时,单独选 优于接在前一段后得到的 。第四项再接上 ,得到子段 ,和为 。
最后一项的 ,但最优子段 在第四项结束,答案为 。固定结尾是为了方便转移,最终仍需比较所有结尾。
初值 来自非空要求,全负数时也必须选一个真实元素,不能把空子段的和 当作答案。
最长上升子序列:枚举倒数第二项的位置
给定长度为 的序列,选择若干个下标递增的元素,使数值严格递增,求最多能选多少个。与连续子段不同,子序列允许跳过元素。
新元素能否接入,取决于已有子序列的末项大小,只保存前若干项中的最长长度不够。因此,同样固定结尾,定义
若只选 ,长度为 ;否则枚举倒数第二项 ,要求 且 。删去 后,剩余子序列以 结尾,可以使用 。
如果不存在满足条件的 ,最大值部分按 处理,表示只选 。
按 递增计算,最终取 。每个状态枚举更早的位置,时间复杂度为 ,空间复杂度为 。
例子:已有的最长子序列未必能接上新元素
已经处理 时,最长长度为 ,可以取 。现在加入 ,这条最长子序列不能接上它,但较短的 可以接上。
固定倒数第二项 后,前面使用哪条以 结尾的子序列,都不会改变 能否接入,因此使用最长的一条即可。枚举所有合法的 ,就覆盖了所有不止一个元素的情况。
对于 ,各位置的状态为
处理最后的 时,可以接在值为 的位置后,最长来源是以 结尾、长度为 的子序列,得到 ,长度为 。值为 的位置虽然也有长度 ,却不满足连接条件。
最大子段和与最长上升子序列都固定了结尾,但允许的连接方式不同:前者要求连续,只能接在第 项后;后者允许跳过元素,需要枚举满足大小关系的更早位置。转移范围由题目的规则决定。
4. 背包限制改变时,重新检查剩下的子问题
恰好装满:先区分可达与不可达
如果题目改为总重量恰好等于 ,较小问题也应改成恰好重量:
仍按第 件选或不选分类。选入后,其他物品的重量也必须恰好为 。所以转移的形式与 0/1 背包相同,但子问题的含义发生了变化。
没有物品时,只有重量 可以达到:
这里用 表示不可达,转移只使用可达来源。按物品数量递增计算,最后查询 ;如果仍不可达,就没有恰好装满的方案。时间与整表空间仍为 。
为什么“恰好装满”不能把初值全设为零
只有重量为 、价值为 的一件物品,容量为 时,上限版的答案为 ,但不存在恰好装满的选法。
状态中的“不超过”与“恰好”规定了不同的子问题。初值全为 ,表示每个容量上限下都有一个空选法;把它用于恰好重量的状态,就会凭空允许不存在的重量。初始化应当从最小问题的真实答案得到。
实现时若用一个有限的极小值标记不可达,应先判断来源可达,再进行加法。
完全背包:选入一件后,仍然允许使用这一种物品
现在有 种物品,每种可以选任意多件。第 种物品的单件重量为 、价值为 ,总重量仍要求不超过容量。
定义 为只使用前 种物品、重量不超过 时的最大价值。仍然观察第 种物品是否被使用。
如果一件都不用,就只使用前 种,得到 。如果至少用一件,先取出其中一件,剩下的物品仍可能包含第 种,所以剩余问题是“使用前 种、容量上限为 ”,而不是只使用前 种。
因为 ,同一行中的 小于 ,可以先按物品种类递增,再在每种物品内按容量递增计算。初始 ,答案为 。时间复杂度为 ,保存整表需要 空间。
重复选入的手算过程,以及一维数组的遍历方向
与 0/1 背包相比,关键变化在第二个候选的物品范围:0/1 背包取出当前物品后,不能再使用它;完全背包取出一件后,还能继续使用这一种物品。
例如只有重量 、价值 的一种物品。容量 时得到 ;容量 时使用本行容量 的答案再加一件,得到 ;容量 时继续得到 。转移允许读取本行,正是在表达物品可以重复使用。
二维写法明确区分了前一种物品的答案和当前种类的答案。压成一维数组后,这两部分答案会在更新过程中暂时共用一段存储,遍历方向必须保证每次读到所需的那一部分。
- 0/1 背包需要读取上一行的 ,因此容量从大到小更新。读取较小容量时,它还没有被当前物品改写。
- 完全背包需要读取本行的 ,因此容量从小到大更新。读取较小容量时,它已经包含当前种类可以重复使用的结果。
仍以重量 、价值 、容量 为例。如果处理一件 0/1 物品时正序更新,容量 刚变成 ,容量 就读取这个新值而变成 ,同一件被使用了两次。完全背包恰好允许这种继续选入,所以正序更新符合它的状态含义。
一维写法把空间降为 ,并没有改变原来的子问题。先确定转移需要上一行还是本行,再确定循环方向。
5. 容量过大时,改求每个价值需要的最小重量
状态能够正确表示问题,还需要能够在数据范围内算出答案。假设有 件 0/1 物品,容量达到 ,而每件价值不超过 。按容量设计的状态虽然仍然正确,但 的计算量过大。
重量上限很大,总价值却至多为 。这时可以改变提问方式:先求出恰好取得每个价值时的最小重量,再判断哪些价值能在容量内取得。
设全部物品的价值和为 ,定义
仍按第 件物品选或不选分类:不选时使用 ;选入时扣除它贡献的价值,再给剩余子问题 加上重量 。
不存在的价值记为不可达,转移只使用可达来源。初始为
对于相同价值,只要最小重量不超过 ,这个价值就能取得;最小重量都超出容量时,其他选法也不可行。因此原问题的答案是
按物品数量递增计算,共有 个状态,每个状态比较两个候选,时间与整表空间复杂度均为 。前述范围中,价值维至多为 ,不再需要枚举到 的容量。
手算:怎样从最小重量找回最大可行价值
容量为 ,三件物品的重量、价值为 。取得价值 的最小重量为 ,选择后两件;取得价值 的最小重量为 ,已经超出容量;三件全选的价值 需要重量 。最终最大可行价值为 。
每一行仍读取上一行的答案,也可以像 0/1 背包一样倒序枚举价值,将空间压到 。
这个状态中,价值成为需要逐个考察的条件,重量成为要优化的结果。物品的选择规则没有改变,但需要回答的较小问题变了。除了检查信息是否足够支持转移,还要观察哪些量的范围较小,以及求出它们以后能否恢复原题要求的答案。
背包按可用物品的范围划分子问题,序列问题还可以固定结尾位置。下一章继续改变观察方式:当一次合并或一次选择会把一整段序列拆成更短的连续段时,以区间为范围定义子问题,再分析这些较短区间的答案怎样组成完整区间的答案。
6. 训练题单
基础模型回顾
以下四题已在基础算法题单中安排。已经能够独立完成的题可以跳过,重点检查状态含义、非空限制和数组更新顺序。
| 顺序 | 题目 | 训练重点 |
|---|---|---|
| 1 | P1115 最大子段和 | 区分“必须以当前位置结尾”与“前若干项中的最优值”,保留非空要求 |
| 2 | P1091 合唱队形 | 从两个方向求结尾状态,再固定峰顶组合答案 |
| 3 | P1049 装箱问题 | 将剩余空间最小转成已用体积最大,并从状态值还原题目答案 |
| 4 | P1616 疯狂的采药 | 解释重复选择同种物品时,为什么可以使用当前层的结果 |
状态与转移训练
以下题目分别改变前驱范围、当前选择或需要优化的量。先根据题意定义较小问题,再确定哪些答案能够用于转移。其中 P1510 已在动态规划强化训练中安排,这里作为改变优化目标的复习题。
| 顺序 | 题目 | 训练重点 |
|---|---|---|
| 5 | P1130 红牌 | 按办理步骤划分阶段,保留所在小组,确定留在原组或换组时的合法前驱 |
| 6 | P2285 打鼹鼠 | 固定最后打中的鼹鼠,用时间差与位置间的距离判断哪些较早事件能够接到当前事件 |
| 7 | P1868 饥饿的奶牛 | 一次加入整个区间,处理闭区间的不重叠条件;辨别它与区间 DP 的区别 |
| 8 | P1799 数列 | 删除会改变剩余元素的位置,状态需要描述已经保留了多少个数 |
| 9 | P1734 最大约数和 | 从不同正整数的选取建立 0/1 背包,区分作为消耗的数值与作为收益的约数和 |
| 10 | P1510 精卫填海 | 将剩余体力最大转成消耗体力最小,处理总体积至少达到要求时的状态与答案 |
| 11 | P5662 纪念品 | 将相邻两天的交易转成一次完全背包,说明收益、可用金币与下一天的关系 |
状态扩展选做
这三题分别增加资源限制、改变状态保存的结果,以及同时处理两条序列。完成前面的题后,再尝试独立设计状态。
| 顺序 | 题目 | 训练重点 |
|---|---|---|
| 12 | P1507 NASA 的食物计划 | 同时保留体积与质量两个上限,判断选入一件食品后剩下什么问题 |
| 13 | P8742 砝码称重 | 每个砝码有放左边、放右边、不放三种选择;保存可达重量差,统计不同正重量 |
| 14 | P1140 相似基因 | 用两条序列各自的处理范围定义子问题,按最后一对是碱基配对还是一侧为空推导转移 |
留言
可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。
正在加载留言区…