第一章:动态规划复习

动态规划进阶目录 · 下一章:区间 DP

1. 什么是动态规划

动态规划(DP)是一种把复杂问题分解成若干个可以逐步求解的子问题的思想。

以最基本的 0/1 背包为例:有 nn 件物品,背包容量为 mm,每件物品至多选一次,求总重量不超过容量时的最大价值。直接面对全部物品,需要同时考虑许多选法,一件物品是否值得选,还取决于它能够和哪些物品搭配。

如果改成逐件考虑物品,假设前面的物品在各个容量下的最优结果已经求出,现在只加入一件物品,就只需考虑选或不选它。此前许多物品的组合问题,已经由较小问题的答案处理完毕。

动态规划的核心表达,是状态设计与转移规划。

  • 状态设计决定怎样重新观察问题,明确每一个较小问题的范围、限制和要求的结果。
  • 转移规划决定怎样拆分一个方案,以及怎样利用较小问题的答案求出当前问题的答案。

2. 0/1 背包:求出前 ii 件物品在每个容量下的最优解

设第 ii 件物品的重量为 wiw_i,价值为 viv_i,重量和价值均为正整数。背包容量 mm 为正整数,允许一件物品都不选。

先把“从全部 nn 件物品中选择”缩小成“只从前 ii 件物品中选择”。加入下一件物品时,还需要为它留出空间,因此不能只求容量 mm 下的答案,而要同时求出不同容量限制下的答案。

定义

fi,j=只从前 i 件物品中选择,总重量不超过 j 时的最大价值。f_{i,j}=\text{只从前 }i\text{ 件物品中选择,总重量不超过 }j\text{ 时的最大价值。}

其中 0≤i≤n0\le i\le n,0≤j≤m0\le j\le m。下标 ii 限定可用物品,jj 是容量上限,不要求恰好用完;原问题对应 fn,mf_{n,m}。

由第 ii 件物品的选与不选推导转移

按第 ii 件物品是否被选分类:

  • 不选:只用前 i−1i-1 件,容量仍为 jj,得到 fi−1,jf_{i-1,j}。
  • 选:先留出容量 wiw_i,其余物品只用前 i−1i-1 件、重量不超过 j−wij-w_i,得到 fi−1,j−wi+vif_{i-1,j-w_i}+v_i。这一类要求 j≥wij\ge w_i。

因此,状态转移方程为

fi,j={fi−1,j,j<wi,max⁡{fi−1,j, fi−1,j−wi+vi},j≥wi.f_{i,j}= \begin{cases} f_{i-1,j},&j<w_i,\\ \max\{f_{i-1,j},\ f_{i-1,j-w_i}+v_i\},&j\ge w_i. \end{cases}

没有物品时,任何容量上限下的最大价值都是 00,因此 f0,j=0f_{0,j}=0。每一行只依赖上一行,按 ii 递增计算,最终取 fn,mf_{n,m}。时间与整表空间复杂度均为 O(nm)O(nm)。

为什么可以直接使用子问题的最大价值

选第 ii 件后,其余物品只受到“来自前 i−1i-1 件、重量不超过 j−wij-w_i”的限制。把它们换成这个限制下的最优选法,仍能与第 ii 件物品一起放入背包,总价值也不会减少。

任意合法方案都属于选或不选中的一类,而两类子问题的合法选法也都能组成原问题的合法方案。因此,比较这两个候选就覆盖了全部可能的最优选法。

直接枚举子集要考察 2n2^n 种选法;现在每个物品范围、每个容量限制下的子问题只求解一次。共有 O(nm)O(nm) 个状态,每个状态只比较两个候选,因此计算量降为 O(nm)O(nm)。

手算:三件物品如何逐行得到答案

背包容量为 66,三件物品的重量、价值分别为

(w1,v1)=(2,4),(w2,v2)=(3,5),(w3,v3)=(4,7).(w_1,v_1)=(2,4),\qquad (w_2,v_2)=(3,5),\qquad (w_3,v_3)=(4,7).

按物品数量逐行计算,可以得到:

可用物品容量 00容量 11容量 22容量 33容量 44容量 55容量 66
没有物品00000000000000
前 11 件00004444444444
前 22 件00004455559999
前 33 件0000445577991111

计算 f2,5f_{2,5} 时,不选第二件得到 f1,5=4f_{1,5}=4;选第二件则先为它留出容量 33,再用剩余容量 22 的最优结果搭配,得到 f1,2+5=9f_{1,2}+5=9。

计算 f3,6f_{3,6} 时,选第三件会给前两件留下容量 22,得到 f2,2+7=11f_{2,2}+7=11;不选第三件则保留 f2,6=9f_{2,6}=9。所以最终答案为 1111,选择第一件和第三件物品。

3. 线性 DP:用结尾位置限定较小问题

对于序列问题,“前若干项中的最优答案”不一定能直接接入新元素。需要根据连接规则,进一步限定较小问题。

最大连续子段和:只延长以第 i−1i-1 项结尾的子段

给定长度为 n≥1n\ge1 的整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n,选择一个连续且非空的子段,求最大的元素和。

只保存前 i−1i-1 项中的最大子段和,无法保证能接上 aia_i。例如 [4,−6,3][4,-6,3] 中,前两项的最优值 44 来自第一项,直接加上第三项就跳过了 −6-6,不再连续。因此,应当固定子段的右端点,定义

fi=必须以第 i 项结尾的最大非空连续子段和。f_i=\text{必须以第 }i\text{ 项结尾的最大非空连续子段和。}

以第 ii 项结尾的子段,或者只包含 aia_i,或者在一个以第 i−1i-1 项结尾的非空子段后面接上 aia_i,因此

f1=a1,fi=max⁡{ai, fi−1+ai}(i≥2).f_1=a_1,\qquad f_i=\max\{a_i,\ f_{i-1}+a_i\}\quad(i\ge2).

按下标递增计算,最终取 max⁡1≤i≤nfi\max_{1\le i\le n}f_i,因为原题没有固定右端点。时间复杂度为 O(n)O(n),只保留前一个状态和全局最优值时,额外空间为 O(1)O(1)。

手算:固定结尾的最优值与前若干项的最优值有什么区别

被延长的子段都以 i−1i-1 结尾,接上同一个 aia_i 后仍然连续,新增的和也相同,因此只需使用其中和最大的子段。

以 [4,−6,3,2,−1][4,-6,3,2,-1] 为例,另记 hih_i 为前 ii 项中的最大子段和:

位置 ii1122334455
元素 aia_i44−6-63322−1-1
必须以 ii 结尾的 fif_i44−2-2335544
前 ii 项中的最优值 hih_i4444445555

计算第三项时,单独选 33 优于接在前一段后得到的 −2+3=1-2+3=1。第四项再接上 22,得到子段 [3,2][3,2],和为 55。

最后一项的 f5=4f_5=4,但最优子段 [3,2][3,2] 在第四项结束,答案为 55。固定结尾是为了方便转移,最终仍需比较所有结尾。

初值 f1=a1f_1=a_1 来自非空要求,全负数时也必须选一个真实元素,不能把空子段的和 00 当作答案。

最长上升子序列:枚举倒数第二项的位置

给定长度为 n≥1n\ge1 的序列,选择若干个下标递增的元素,使数值严格递增,求最多能选多少个。与连续子段不同,子序列允许跳过元素。

新元素能否接入,取决于已有子序列的末项大小,只保存前若干项中的最长长度不够。因此,同样固定结尾,定义

fi=必须以 ai 结尾的最长严格上升子序列长度。f_i=\text{必须以 }a_i\text{ 结尾的最长严格上升子序列长度。}

若只选 aia_i,长度为 11;否则枚举倒数第二项 aja_j,要求 j<ij<i 且 aj<aia_j<a_i。删去 aia_i 后,剩余子序列以 aja_j 结尾,可以使用 fjf_j。

fi=1+max⁡1≤j<iaj<aifj.f_i=1+\max_{\substack{1\le j<i\\a_j<a_i}}f_j.

如果不存在满足条件的 jj,最大值部分按 00 处理,表示只选 aia_i。

按 ii 递增计算,最终取 max⁡1≤i≤nfi\max_{1\le i\le n}f_i。每个状态枚举更早的位置,时间复杂度为 O(n2)O(n^2),空间复杂度为 O(n)O(n)。

例子:已有的最长子序列未必能接上新元素

已经处理 [1,4,7,2][1,4,7,2] 时,最长长度为 33,可以取 [1,4,7][1,4,7]。现在加入 33,这条最长子序列不能接上它,但较短的 [1,2][1,2] 可以接上。

固定倒数第二项 jj 后,前面使用哪条以 aja_j 结尾的子序列,都不会改变 aia_i 能否接入,因此使用最长的一条即可。枚举所有合法的 jj,就覆盖了所有不止一个元素的情况。

对于 [1,4,7,2,3,6][1,4,7,2,3,6],各位置的状态为

(f1,f2,f3,f4,f5,f6)=(1,2,3,2,3,4).(f_1,f_2,f_3,f_4,f_5,f_6)=(1,2,3,2,3,4).

处理最后的 66 时,可以接在值为 1,4,2,31,4,2,3 的位置后,最长来源是以 33 结尾、长度为 33 的子序列,得到 [1,2,3,6][1,2,3,6],长度为 44。值为 77 的位置虽然也有长度 33,却不满足连接条件。

最大子段和与最长上升子序列都固定了结尾,但允许的连接方式不同:前者要求连续,只能接在第 i−1i-1 项后;后者允许跳过元素,需要枚举满足大小关系的更早位置。转移范围由题目的规则决定。

4. 背包限制改变时,重新检查剩下的子问题

恰好装满:先区分可达与不可达

如果题目改为总重量恰好等于 mm,较小问题也应改成恰好重量:

ei,j=前 i 件物品中,总重量恰好为 j 的最大价值。e_{i,j}=\text{前 }i\text{ 件物品中,总重量恰好为 }j\text{ 的最大价值。}

仍按第 ii 件选或不选分类。选入后,其他物品的重量也必须恰好为 j−wij-w_i。所以转移的形式与 0/1 背包相同,但子问题的含义发生了变化。

没有物品时,只有重量 00 可以达到:

e0,0=0,e0,j=−∞(j>0).e_{0,0}=0,\qquad e_{0,j}=-\infty\quad(j>0).

这里用 −∞-\infty 表示不可达,转移只使用可达来源。按物品数量递增计算,最后查询 en,me_{n,m};如果仍不可达,就没有恰好装满的方案。时间与整表空间仍为 O(nm)O(nm)。

为什么“恰好装满”不能把初值全设为零

只有重量为 22、价值为 33 的一件物品,容量为 33 时,上限版的答案为 33,但不存在恰好装满的选法。

状态中的“不超过”与“恰好”规定了不同的子问题。初值全为 00,表示每个容量上限下都有一个空选法;把它用于恰好重量的状态,就会凭空允许不存在的重量。初始化应当从最小问题的真实答案得到。

实现时若用一个有限的极小值标记不可达,应先判断来源可达,再进行加法。

完全背包:选入一件后,仍然允许使用这一种物品

现在有 nn 种物品,每种可以选任意多件。第 ii 种物品的单件重量为 wi>0w_i>0、价值为 vi>0v_i>0,总重量仍要求不超过容量。

定义 ci,jc_{i,j} 为只使用前 ii 种物品、重量不超过 jj 时的最大价值。仍然观察第 ii 种物品是否被使用。

如果一件都不用,就只使用前 i−1i-1 种,得到 ci−1,jc_{i-1,j}。如果至少用一件,先取出其中一件,剩下的物品仍可能包含第 ii 种,所以剩余问题是“使用前 ii 种、容量上限为 j−wij-w_i”,而不是只使用前 i−1i-1 种。

ci,j={ci−1,j,j<wi,max⁡{ci−1,j, ci,j−wi+vi},j≥wi.c_{i,j}= \begin{cases} c_{i-1,j},&j<w_i,\\ \max\{c_{i-1,j},\ c_{i,j-w_i}+v_i\},&j\ge w_i. \end{cases}

因为 wi>0w_i>0,同一行中的 j−wij-w_i 小于 jj,可以先按物品种类递增,再在每种物品内按容量递增计算。初始 c0,j=0c_{0,j}=0,答案为 cn,mc_{n,m}。时间复杂度为 O(nm)O(nm),保存整表需要 O(nm)O(nm) 空间。

重复选入的手算过程,以及一维数组的遍历方向

与 0/1 背包相比,关键变化在第二个候选的物品范围:0/1 背包取出当前物品后,不能再使用它;完全背包取出一件后,还能继续使用这一种物品。

例如只有重量 22、价值 33 的一种物品。容量 22 时得到 33;容量 44 时使用本行容量 22 的答案再加一件,得到 66;容量 66 时继续得到 99。转移允许读取本行,正是在表达物品可以重复使用。

二维写法明确区分了前一种物品的答案和当前种类的答案。压成一维数组后,这两部分答案会在更新过程中暂时共用一段存储,遍历方向必须保证每次读到所需的那一部分。

  • 0/1 背包需要读取上一行的 fi−1,j−wif_{i-1,j-w_i},因此容量从大到小更新。读取较小容量时,它还没有被当前物品改写。
  • 完全背包需要读取本行的 ci,j−wic_{i,j-w_i},因此容量从小到大更新。读取较小容量时,它已经包含当前种类可以重复使用的结果。

仍以重量 22、价值 33、容量 44 为例。如果处理一件 0/1 物品时正序更新,容量 22 刚变成 33,容量 44 就读取这个新值而变成 66,同一件被使用了两次。完全背包恰好允许这种继续选入,所以正序更新符合它的状态含义。

一维写法把空间降为 O(m)O(m),并没有改变原来的子问题。先确定转移需要上一行还是本行,再确定循环方向。

5. 容量过大时,改求每个价值需要的最小重量

状态能够正确表示问题,还需要能够在数据范围内算出答案。假设有 100100 件 0/1 物品,容量达到 10910^9,而每件价值不超过 100100。按容量设计的状态虽然仍然正确,但 O(nm)O(nm) 的计算量过大。

重量上限很大,总价值却至多为 10410^4。这时可以改变提问方式:先求出恰好取得每个价值时的最小重量,再判断哪些价值能在容量内取得。

设全部物品的价值和为 VV,定义

gi,t=只从前 i 件物品中选择,恰好取得价值 t 时的最小总重量。g_{i,t}=\text{只从前 }i\text{ 件物品中选择,恰好取得价值 }t\text{ 时的最小总重量。}

仍按第 ii 件物品选或不选分类:不选时使用 gi−1,tg_{i-1,t};选入时扣除它贡献的价值,再给剩余子问题 gi−1,t−vig_{i-1,t-v_i} 加上重量 wiw_i。

gi,t={gi−1,t,t<vi,min⁡{gi−1,t, gi−1,t−vi+wi},t≥vi.g_{i,t}= \begin{cases} g_{i-1,t},&t<v_i,\\ \min\{g_{i-1,t},\ g_{i-1,t-v_i}+w_i\},&t\ge v_i. \end{cases}

不存在的价值记为不可达,转移只使用可达来源。初始为

g0,0=0,g0,t=+∞(t>0).g_{0,0}=0,\qquad g_{0,t}=+\infty\quad(t>0).

对于相同价值,只要最小重量不超过 mm,这个价值就能取得;最小重量都超出容量时,其他选法也不可行。因此原问题的答案是

max⁡{t∣0≤t≤V, gn,t≤m}.\max\{t\mid 0\le t\le V,\ g_{n,t}\le m\}.

按物品数量递增计算,共有 O(nV)O(nV) 个状态,每个状态比较两个候选,时间与整表空间复杂度均为 O(nV)O(nV)。前述范围中,价值维至多为 10410^4,不再需要枚举到 10910^9 的容量。

手算:怎样从最小重量找回最大可行价值

容量为 77,三件物品的重量、价值为 (6,4),(4,3),(3,3)(6,4),(4,3),(3,3)。取得价值 66 的最小重量为 77,选择后两件;取得价值 77 的最小重量为 99,已经超出容量;三件全选的价值 1010 需要重量 1313。最终最大可行价值为 66。

每一行仍读取上一行的答案,也可以像 0/1 背包一样倒序枚举价值,将空间压到 O(V)O(V)。

这个状态中,价值成为需要逐个考察的条件,重量成为要优化的结果。物品的选择规则没有改变,但需要回答的较小问题变了。除了检查信息是否足够支持转移,还要观察哪些量的范围较小,以及求出它们以后能否恢复原题要求的答案。

背包按可用物品的范围划分子问题,序列问题还可以固定结尾位置。下一章继续改变观察方式:当一次合并或一次选择会把一整段序列拆成更短的连续段时,以区间为范围定义子问题,再分析这些较短区间的答案怎样组成完整区间的答案。

6. 训练题单

基础模型回顾

以下四题已在基础算法题单中安排。已经能够独立完成的题可以跳过,重点检查状态含义、非空限制和数组更新顺序。

顺序题目训练重点
1P1115 最大子段和区分“必须以当前位置结尾”与“前若干项中的最优值”,保留非空要求
2P1091 合唱队形从两个方向求结尾状态,再固定峰顶组合答案
3P1049 装箱问题将剩余空间最小转成已用体积最大,并从状态值还原题目答案
4P1616 疯狂的采药解释重复选择同种物品时,为什么可以使用当前层的结果

状态与转移训练

以下题目分别改变前驱范围、当前选择或需要优化的量。先根据题意定义较小问题,再确定哪些答案能够用于转移。其中 P1510 已在动态规划强化训练中安排,这里作为改变优化目标的复习题。

顺序题目训练重点
5P1130 红牌按办理步骤划分阶段,保留所在小组,确定留在原组或换组时的合法前驱
6P2285 打鼹鼠固定最后打中的鼹鼠,用时间差与位置间的距离判断哪些较早事件能够接到当前事件
7P1868 饥饿的奶牛一次加入整个区间,处理闭区间的不重叠条件;辨别它与区间 DP 的区别
8P1799 数列删除会改变剩余元素的位置,状态需要描述已经保留了多少个数
9P1734 最大约数和从不同正整数的选取建立 0/1 背包,区分作为消耗的数值与作为收益的约数和
10P1510 精卫填海将剩余体力最大转成消耗体力最小,处理总体积至少达到要求时的状态与答案
11P5662 纪念品将相邻两天的交易转成一次完全背包,说明收益、可用金币与下一天的关系

状态扩展选做

这三题分别增加资源限制、改变状态保存的结果,以及同时处理两条序列。完成前面的题后,再尝试独立设计状态。

顺序题目训练重点
12P1507 NASA 的食物计划同时保留体积与质量两个上限,判断选入一件食品后剩下什么问题
13P8742 砝码称重每个砝码有放左边、放右边、不放三种选择;保存可达重量差,统计不同正重量
14P1140 相似基因用两条序列各自的处理范围定义子问题,按最后一对是碱基配对还是一侧为空推导转移

留言

可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。