Acwing算法基础课：动态规划

动态规划

内容部分来自：什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 阮行止的回答 - 知乎

Widely-known Definition

无后效性：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。

最优子结构：大问题的最优解可以由小问题的最优解推出。

使用动态规划的条件：能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。

“闫氏”集合分析法

（以01背包问题为例）

DP为什么会快？

无论是DP还是暴力，我们的算法都是在可能解空间内，寻找最优解。

来看钞票问题。暴力做法是枚举所有的可能解，这是最大的可能解空间。 DP是枚举有希望成为答案的解。这个空间比暴力的小得多。

也就是说：DP自带剪枝。

DP舍弃了一大堆不可能成为最优解的答案。譬如：

• 15 = 5+5+5 被考虑了。
• 15 = 5+5+1+1+1+1+1 从来没有考虑过，因为这不可能成为最优解。

从而我们可以得到DP的核心思想：尽量缩小可能解空间。

在暴力算法中，可能解空间往往是指数级的大小；如果我们采用DP，那么有可能把解空间的大小降到多项式级。

一般来说，解空间越小，寻找解就越快。这样就完成了优化。

如何设计DP算法

下面介绍比较通用的设计DP算法的步骤。

首先，把我们面对的局面表示为x。这一步称为设计状态。对于状态x，记我们要求出的答案(e.g. 最小费用)为f(x).我们的目标是求出f(T)。找出f(x)与哪些局面有关（记为p），写出一个式子（称为状态转移方程），通过f(p)来推出f(x)。

设计DP算法，往往可以遵循DP三连：

• 我是谁？ ——设计状态，表示局面
• 我从哪里来？
• 我要到哪里去？ ——设计转移

设计状态是DP的基础。接下来的设计转移，有两种方式：一种是考虑我从哪里来（本文之前提到的两个例子，都是在考虑“我从哪里来”）；另一种是考虑我到哪里去，这常见于求出f(x)之后，更新能从x走到的一些解。这种DP也是不少的，我们以后会遇到。

总而言之，“我从哪里来”和“我要到哪里去”只需要考虑清楚其中一个，就能设计出状态转移方程，从而写代码求解问题。前者又称pull型的转移，后者又称push型的转移。

DP算法的两种实现方式

DP能实现的前提：状态间的依赖关系是DAG，即不能有环

• 按顺序递推：对于容易找到依赖关系规律，计算顺序明确的（线性DP/区间DP）
• 记忆化搜索：不容易找到依赖关系规律，计算顺序不明确的（区间DP/“滑雪”）

DP算法的时间复杂度计算

一般是状态数×状态转移计算量

背包问题

01背包问题

\[f[i][j] = \max\{f[i-1][j], f[i-1][j-v_i] + w_i\};\]

可注意到两个特点：

• 第一分量只依赖于上一层（$i-1$）
• 第二份量都$\le j$

由此代码中第二层循环逆序遍历的情况下，状态表可减为一维。

for (int i=1; i<=n; i++) 
    for (int j=m; j>=v[i]; j--) 
        f[j] = max(f[j], f[j-v[i]] + w[i]);

完全背包问题

\[\begin{equation} f[i][j] = \max\{f[i-1][j], f[i-1][j-v_i]+w_i, f[i-1][j-2v_i]+2w_i, ..., f[i-1][j-kv_i]+kw_i\} \end{equation}\]

其中$j>=kv_i$​​。若直接按此公式递推，时间复杂度$O(N^2V)$。

由于

\[\begin{equation} f[i][j-v_i] = \max\{f[i-1][j-v_i], f[i-1][j-2v_i]+w_i, f[i-1][j-3v_i]+2w_i, ..., f[i-1][j-kv_i]+(k-1)w_i\} \end{equation}\]

“错位相减”可得

\[\begin{equation} f[i][j] = \max\{f[i-1][j], f[i][j-v_i]+w_i\} \end{equation}\]

同样地，观察第一、第二分量的特点，可在第二层循环顺序遍历的情况下，将代码中状态表优化为一维的。优化本质上是利用了先前已计算的状态，避免重复计算。这样，时间复杂度降到了$O(NV)$。

for (int i=1; i<=n; i++)
    for (int j=v[i]; j<=m; j++)
        f[j] = max(f[j], f[j-v[i]] + w[i]);

可发现，优化后的01背包和完全背包代码中，区别仅在于第二层循环的遍历顺序。

多重背包问题

\[f[i][j] = \max\{f[i-1][j], f[i-1][j-v_i]+w_i, f[i-1][j-2v_i]+2w_i, ..., f[i-1][j-kv_i]+kw_i\}\]

其中，满足$k\le min{\frac{j}{v_i}, s_i}$，$s_i$是第$i$个物品的数量。仍可以暴力求解，复杂度$O(N^2V)$。

由于上面k与完全背包不同的条件，得不出公式(2)，无法与(1)“错位相减”，不能用完全背包的优化方法。

二进制优化

对于每一种物品，提供$\log s_i$种“打包”，每个包中该物品的数量分别为：

\[1, 2, 4, ..., 2^k \\ 或\\ 1, 2, 4, ..., 2^k, c\]

其中$c\gt 0$， $k$是最大的取值使得$1+2+4+…+2^k(+c)=s_i$。由此，$1, 2, 4, …, 2^k$的组合可表示0~$2^{k+1}-1$的数，加上c可表示c~$s_i$的数，由于$c<2^{k+1}$（否则k可取更大值），这些数的组合能够“可重、不漏、不多”地表示0~$s_i$的每一个数。

于是多重背包问题可转换为一个01背包问题，时间复杂度$O(NV\log s)$​。

int cnt = 0; // 将输入在线“打包”转为01背包问题
for (int i=1; i<=n; i++) {
    int a, b, s;
    scanf("%d%d%d", &a, &b, &s);
    int k=1;
    while (k <= s) {
        v[++cnt] = k*a;
        w[cnt] = k*b;
        s -= k;
        k <<= 1;
    }
    if (s > 0) {
        v[++cnt] = s*a;
        w[cnt] = s*b;
    }
}
n = cnt;
for (int i=1; i<=n; i++) // 一趟01背包模板
    for (int j=m; j>=v[i]; j--)
        f[j] = max(f[j], f[j-v[i]]+w[i]);

printf("%d\n", f[m]);

优先队列优化

TBD

分组背包问题

trivial

for (int i=1; i<=n; i++)
        for (int j=m; j>=0; j--)
            for (int k=1; k<=s[i]; k++)
                if (j>=v[i][k])
                    f[j] = max(f[j], f[j-v[i][k]]+w[i][k]);

时间复杂度$O(NVS)$。

线性DP

数字三角形

都是求路径最大和，自顶向下和自底向上是一样的（“无向图”）：

• 自顶向下：需判断边界/初始化边界为负无穷，最后需要求最值
• 自底向上：不需判断边界，不需求最值

另外，使用边界（用-INF填充）可避免if判断

最长上升子序列

$f[i]$ 定义为所有以$a_i$结尾的上升子序列中的最长长度

\[f[i] = \max\{0,f[j]\}+1 \\ 其中j=1,2,...,i-1且a_j<a_i\]

时间复杂度$O(n^2)$​

$O(n \log n)$ 做法*

定义$q[i]$为当前所有长度为$i$的上升子序列结尾数的最小值，可以证明$q[i]$​单调递增（不严格）（可反证）

于是可二分查找$q[j] < a_i$的边界$j$，$f[i] = j+1$

同时更新$q[]$：因为$q[j+1]\ge a_i$，所以直接令$q[j+1]=a_i$即可。

最长公共子序列

定义$f[i][j]$为串$a[1…i]$和$b[1…j]$的最长公共子序列长度

\[f[i][j] = \begin{cases} \max\{f[i-1][j-1]+1, f[i-1][j], f[i][j-1]\} & a_i=b_j\\ \max\{f[i-1][j], f[i][j-1]\} & a_i\neq b_j \end{cases}\]

最短编辑距离*

定义$f[i][j]$为将串$a[1…i]$变为$b[1…j]$的最小操作次数

状态转移时，只考虑对$a[i]$​​的操作即可，原因证明较复杂，参考acwing讨论区

不严谨理解：对每个操作序列，如果存在对最后一个字符的操作，则都可以等价地将该操作移到最后执行

\[f[i][j] = \min \{f[i-1][j]+1, f[i][j-1]+1, \begin{cases} f[i-1][j-1]+1 & a_i \neq b_j \\ f[i-1][j-1] & a_i = b_j \end{cases} \}\]

初始化：$f[0][j]=j, f[i][0]=i, 1\le i \le n, 1\le j \le m$

区间DP

石子合并

定义$f[i][j]$为合并区间$[i, j]$的石子为一堆的最小代价

\[f[i][j]=\min\{f[i][k]+f[k+1][j] \mid k=i,i+1,...,j-1\}+\sum_{m=i}^{j}w_m\]

初始值$f[i][i]=0$

按区间长度依次迭代递推：$2,3,4,…,n$

时间复杂度：$O(n^2 \cdot n) = O(n^3)$

计数类DP

整数划分

方法1

定义$f[i][j]$为整数$i$的所有最大值为$j$​的划分的数量

\[f[i][j] = \begin{cases} \sum_{k=1}^{\min\{j, i-j\}} f[i-j][k] & j\lt i \\ 1 & j=i \end{cases}\]

求和部分可用前缀和优化，时间复杂度$O(n^2)$

方法2

定义$f[i][j]$为所有总和为$i$，表示成$j$个数的和的方案数

\[f[i][j] = f[i-1][j-1]+f[i-j][j]\]

可分为两部分：最小值为1的方案（$f[i-1][j-1]$），和最小值大于1的方案（$f[i-j][j]$，每个数减一）。

方法3

遵循完全背包问题的思路，有类似的定义：定义$f[i][j]$为考虑数$1$~$i$，总和为$j$​的方案数

朴素版本时间复杂度$O(n^2 \log n)$，经与完全背包类似的公式化简（“错位相减”）可达到$O(n^2)$。

\[f[i][j] = f[i-1][j] + f[i][j-i]\]

数位统计、状态压缩DP

跳了

树形DP

没有上司的舞会

定义$f[i][j]$为以节点$i$为根节点的子树，选择节点$i$（$j=1$）/不选择节点$i$（$j = 0$）时子树中选择节点权值和的最大值

对节点$x$，其子节点$v_i$（若有）​：

\[f[x][0] = \sum_i \max \{f[v_i][0], f[v_i][1]\} \\ f[x][1] = \sum_i f[v_i][0] + w_x\]

状态转移依赖于子节点，所以可在DFS过程中后序遍历树，填充DP表；使用邻接表存树，只存出边即可

DP表初始化：全填0即可

记忆化搜索

滑雪

定义$f[i][j]$为从$(i, j)$出发的最大轨迹长度

\[f[i][j] = \max \{ f[i-1][j], f[i][j+1], f[i+1][j], f[i][j-1] \} + 1\]

使用一般的递推难以计算DP表（可能需要先算“无路可走”的格子，再算“有一路可走”的格子……），适用记忆化搜索

记忆化搜索是DP的一种实现方式，但仍需要满足前提：状态依赖关系中不存在环

此问题的性质保证了不存在环：因为轨迹上要求高度严格递减