课件，补充资料

动态规划

纸币问题 1（P2842）

贪心的思路有问题，在面额为 1,5,111,5,11 元时不是最优解。

我们可以使用 dfs 求解，但是因为重复计算，所以效率很低。

将每个面额计算后的值记录下来，下次再使用直接返回。时间复杂度 O(nw)O(nw)。这种方法叫做记忆化搜索。

我们可以直接使用数组计算，从面额为 11 枚举到面额为 ww，计算每个面额需要多少张纸币。

数字三角形（P1216）

贪心依然不对。可以使用效率较低的 dfs。

把每个点到底端路径的最大值存下来，就是记忆化搜索。

利用记忆化搜索的思想，直接用数组解决，就是 dp。

状态、转移与有向无环图

状态

问题所在的局面，即“凑够 ww 元需要多少张”“从 (x,y)(x,y) 走到最下层的最大数字和”。状态的定义是明确的，具有无后效性以及最优子结构性质。

如何确定状态成了关键问题，可以使用朴素的搜索算法推出状态。

转移

转移是状态之间的关系，类似于递推。通过“状态转移方程”来描述。

有向无环图

把状态看成节点，把转移看成有向边，那么 dp 的模型可以看成一个有向无环图。

我们按照拓扑序遍历整张图即可解决问题。绝大多数 dp 对于遍历的顺序或层次是明显的，我们称之为阶段。

解题思路

  1. 确定状态
  2. 寻找转移
  3. 划分阶段
  4. 按照顺序求解

背包

纸币问题 2（P2840）

fi=∑j=1nfi−ajf_i=\sum_{j=1}^n f_{i-a_j}

纸币问题 3（P2834）

采药（P1048）

经典 01 背包板子。

定义 fi,jf_{i,j} 为采前 ii 株用时 jj 的最大价值。

fi,j=max⁡{fi−1,j−ti+vi,fi−1,j}f_{i,j}=\max\{f_{i-1,j-t_i}+v_i,f_{i-1,j}\}

我们可以缩掉第一维，然后倒着走。

fj=max⁡{fj−ti+vi,fj}f_j=\max\{f_{j-t_i}+v_i,f_j\}

疯狂的采药（P1616）

完全背包板子。

01 背包内层循环改成正着走即可。

线性 dp

线性状态动态规划是一类状态定义与题设内容线性相关的 dp。

LIS（最长上升子序列）问题

给出长为 n≤105n \le 10^5 的正整数序列 aa，求序列中最长上升子序列的长度。

定义 fif_i 为以 ii 结尾的最长长度。

fi=max⁡j<i∧aj≤ai{fj}+1f_i=\max_{j<i \land a_j\le a_i}\{f_j\}+1

LCS（最长公共子序列）问题（P1439）

子序列：从序列中删掉若干个数剩下的序列。

定义 fi,jf_{i,j} 为 AA 中前 ii 个数与 BB 中前 jj 个数的 LCS 长度，最终答案是 fn,mf_{n,m}。

fi,j={fi−1,j−1+1,Ai=Bjmax⁡{fi−1,j,fi,j−1},Ai≠Bjf_{i,j}=\begin{cases} f_{i-1,j-1}+1,A_i=B_j\\ \max\{f_{i-1,j},f_{i,j-1}\},A_i\ne B_j\\ \end{cases}

编辑距离（P2758）

定义 fi,jf_{i,j} 为将 A1∼iA_{1\sim i} 转换为 B1∼jB_{1\sim j} 的最少次数，f0,0=1f_{0,0}=1。

  1. 删除 fi,j=min⁡{fi,j−1,fj,i−1}+1f_{i,j}=\min\{f_{i,j-1},f_{j,i-1}\}+1
  2. 插入 fi,j=min⁡{fi,j−1,fj,i−1}+1f_{i,j}=\min\{f_{i,j-1},f_{j,i-1}\}+1
  3. 修改 fi,j={fi−1,j−1,Ai=Bjfi−1,j−1+1,Ai≠Bjf_{i,j}=\begin{cases}f_{i-1,j-1},A_i=B_j\\f_{i-1,j-1}+1,A_i\ne B_j\end{cases}

高维线性 dp

有一个 nn 层的数字金字塔，你有 k(k≤n)k(k\le n) 次机会，每次可以将金字塔中的任何一个数字乘以 33（不能对同一个数字反复成乘 33），求从最高点到底部任意一点的最大数字和（每一步只能往下走）。n≤100n \le 100。

使用数字金字塔的转移方程无法体现出 kk 次乘 33 限制。因此定义 fi,j,kf_{i,j,k} 为走到 (i,j)(i,j) 且使用了 kk 次乘 33。

有向左且乘 33，向左不乘 33，向右且乘 33，向右不乘 33 四种转移。

初始化定义 f1,1,0=a1,1,f1,1,1=3×a1,1f_{1,1,0}=a_{1,1},f_{1,1,1}=3\times a_{1,1}，最终答案为 f1,1,kf_{1,1,k}。

区间 dp

区间 dp 比较明显的特征是其状态定义通常包括区间信息 (l,r)(l,r)，转移也通常为从子区间扩展到当前区间。

回文字串（IOI2000 T1 / P1435）

定义 fl,rf_{l,r} 为将区间 (l,r)(l,r) 变为回文的最小操作数。

fl,r={fl+1,r−1+1,sl=srmin⁡{fl+1,r+1,fl,r−1+1},sl≠srf_{l,r}=\begin{cases} f_{l+1,r-1}+1,s_l=s_r\\ \min\{f_{l+1,r}+1,f_{l,r-1}+1\},s_l\ne s_r\\ \end{cases}

石子合并（P1775）

定义 fl,rf_{l,r} 为将区间 (l,r)(l,r) 合为一堆的最小代价。

fl,r=min⁡l≤k≤r{fl,k+fk+1,r}+sumr−suml−1f_{l,r}=\min_{l\le k\le r}\{f_{l,k}+f_{k+1,r}\}+sum_r-sum_{l-1}

合唱队（HNOI2010 / P3205）

环形 dp

石子合并（NOI1995 / P1880）

断环成链，然后倍长链，每次取一个长度为 nn 的子区间，滑动 nn 次。

环上最大独立集（T321589）

定义 fi,0/1f_{i,0/1} 为前 ii 个最大答案，第 ii 个是否选择。

fi,0=max⁡{fi−1,0,fi−1,1}f_{i,0}=\max\{f_{i-1,0},f_{i-1,1}\}

fi,1=fi−1,0+aif_{i,1}=f_{i-1,0}+a_i

最终答案为 max⁡{fn,0,fn,1}\max\{f_{n,0},f_{n,1}\}。

但是这种方法是在链上的，在环上无法断环成链。

可以先忽略成环的一条边，然后对剩下的部分进行 dp，最后考虑这条边的影响。