26.动态规划入门

发表于 2025-04-16 更新于 2025-04-24 分类于 ACM ， ACMCOURSE

动态规划入门

动态（Dynamic）：问题的解因时间或决策而变化
规划（Programming）：分解子问题，利用子问题之间关系求解

递推与带备忘递归

数字三角形：从顶部出发，只能沿箭头走，到底部的哪个路线经过的所有数字之和最大

给每个格子编号

思考 2 件事：

最优子结构：数学化定义问题，分析该问题哪些更小规模的子问题的解可以直接影响它的解
- 定义 \(d(i,j)\) 是从 \((i,j)\) 出发到底的最大和
- 可知 \(d(1,1)\) 是问题的最优解
- \(d(i,j)\) 与 \(d(i+1,j)\)、\(d(i+1,j+1)\) 直接相关——有这俩就能确定 \(d(i,j)\)
状态转移方程：对于特定规模的问题，能直接影响它的子问题以什么方式计算能推导到它
- 设 \(a(i,j)\) 是 \((i,j)\) 格子的值
- \(d(i,j)=a(i,j)+\max(d(i+1,j),d(i+1,j+1))\)

动态规划的两种等价实现方法，渐进复杂度通常一致

自底向上的递推

从小到大逐个解决子问题

优势：没有频繁的递归调用，常数更小

劣势：思维量——需要预先确定好子问题规模大小，即求解的顺序

int DP() {
    for(int j = 1; j <= n; j ++) dp[n][j] = a[n][j];
    for(int i = n - 1; i >= 1; i --)    // 自底向上递推
        for(int j = 1; j <= i; j ++)
            dp[i][j] = std::max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j];
    return dp[1][1];
}

自顶向下的带备忘递归（记忆化搜索）

对需要但尚未解决的子问题进行递归求解，否则直接返回备忘

优势：

思维量相对小，直接按状态转移方程实现
有的特殊情况下能跳过很多子问题

劣势：递归开销，甚至面对有些过大的问题没有足够的递归栈

int DPS(int i, int j) {
    if(i > n) return 0;
    int &ans = dp[i][j];
    if(ans != -1) return ans;
    ans = std::max(DPS(i + 1, j), DPS(i + 1, j + 1)) + a[i][j];
    return ans;
}

有向无环图DP

有向无环图（Directed Acyclic Graph，DAG）是指不存在环的有向图，从任意点出发沿有向边走，不会再回到该点。

很多动态规划问题可以转换为DAG上的最长/最短路或路径计数。

例：矩形嵌套

给出一系列矩形的长和宽，矩形𝐴能够嵌套在𝐵内部当且仅当𝐴的长与宽都对应严格小于𝐵的长与宽，求这些矩形能够组成的最深嵌套

构建DAG：

最优子结构：

"可嵌套"关系可以建模为图：\((i,j)\in E\)表示\(j\)能嵌套在\(i\)内，有向边\(i\rightarrow j\)，该图是DAG
\(d(i)\)表示\(i\)为最外层时的最深嵌套，只与\((i,j)\in E\)的\(j\)有关

状态转移方程：

\(d(i)=\max\{d(j)+1|(i,j)\in E\}\)

int DPS(int i) {
    int &ans = dp[i];
    if(ans != -1) return ans;
    ans = 1;    // 至少包含自身
    for(int j = 1; j <= n; j ++) 
        if(g[i][j] && DPS(j) + 1 > ans){
            ans = DPS(j) + 1; 
        } 
    return ans;
}

思考：如果不止要求最深嵌套层数，还要求把最深嵌套的各个节点按顺序输出，怎么做？

提示：状态转移时记录转移方向

复杂度分析：

要填一个dp[]，有\(O(n)\)项。每一项要一个\(O(n)\)的循环才能得到最终结果，所以\(O(n^2)\)。

知识点：动态规划的复杂度分析技巧。动态规划就是一个"填表游戏"，其复杂度就由表的大小和完成表的每一项最坏情况的复杂度决定。

扩展题：有\(n\)种立方体（每种数量无限），选一些堆成尽可能高的柱子，上方的立方体底面长宽必须严格小于下方的立方体。

提示：立方体可以任选一个棱作为高，则另外两个棱构成底面长宽。

区间DP

例：括号匹配

给定一个只包含{}、()、[]的字符串括号嵌套可能不合法，如"{(] )" 给出添加符号最少的方案，使括号嵌套合法

最优子结构：

\(d(i,j)\) 表示 \([i, j]\) 这段符号的最优解，即最少添加使之合法的方案
可以从 3 个方向转移
- 左边加一个让 \(j\) 匹配
- 右边加一个让 \(i\) 匹配，
- 如果\(i\)和\(j\)位置恰好匹配，那么不用加，让它俩匹配

状态转移方程：

\(d(i,j)=\begin{cases} \min(d(i+1,j-1), d(i+1,j)+1, d(i,j-1)+1) & \text{如果}s[i]\text{和}s[j]\text{匹配} \\ \min(d(i+1,j)+1, d(i,j-1)+1) & \text{否则} \end{cases}\)

例：矩阵链乘法

还没学过线性代数的同学，可以简单了解下矩阵是什么，如何相乘：

两个矩阵相乘，则第一个的列数必须等于第二个的行数，比如第一个 \(a\times b\)，第二个必须 \(b\times c\)

矩阵相乘的结果是第一个的行数、第二个的列数，即\(a\times b\) 和 \(b\times c\) 两个矩阵相乘得到 \(a \times c\)

相乘方式：结果矩阵的 \((i,j)\) 位置的值，是前一个的第 \(i\) 行与后一个的第 \(j\) 列一一对应相乘再加起来的结果
1
2
3
4
5
6
7
8
9
10
int x[a][b], y[b][c], z[a][c];
// ...
for(int i = 0; i < a; i ++) {
    for(int j = 0; j < c; j ++) {
        z[i][j] = 0;
        for(int k = 0; k < b; k ++) {
            z[i][j] += x[i][k] * y[k][j];
        }
    }
}
两个矩阵的基本元素乘法次数也显而易见了

计算\(n\)个矩阵序列的乘积\(A_1 A_2\cdots A_n\)，矩阵规模保证能够合法相乘。

矩阵乘满足结合律，任何加括号方法计算结果相同。不同加括号方式，元素相乘次数不同。求一个矩阵乘法次序，使得元素相乘次数最少。

例：\(\langle A_1,A_2,A_3 \rangle\)规模分别为\(10\times 100\)、\(100\times 5\)、\(5\times 50\)

\(((A_1 A_2 ) A_3)\)：\(10\cdot 100\cdot 5+10\cdot 5\cdot 50=7500\)次
\((A_1 (A_2 A_3))\)：\(100\cdot 5\cdot 50+10\cdot 100\cdot 50=75000\)次

最优子结构：

最后一次矩阵乘法可以发生在任意位置\(k\)，即\((A_1\cdots A_k)(A_{k+1}\cdots A_n)\)
\(d(i,j)\)：\(A_i A_{i+1}\cdots A_{j-1} A_j\)这一区间的最优解
每一个\(k\)作为该区间最后一次乘法，都是潜在的最优方案
对应子问题为\(d(i,k)\)与\(d(k+1,j)\)

状态转移方程：

设\(p_0,p_1,\dots,p_n\)是矩阵序列的规模，如\(A_1\)为\(p_0\times p_i\)，\(A_i\)为\(p_{i-1}\times p_i\)
\[ d(i,j)=\begin{cases} 0 & \text{如果}i=j \\ \min\limits_{i\leq k\leq j}\{d(i,k)+d(k+1,j)+p_{i-1}p_kp_j\} & \text{如果}i<j \end{cases} \]

int DPS(int l, int r) {
    // 基本情况：如果区间长度为1，不需要乘法
    if(l == r - 1) return 0;
    
    // 使用引用减少重复代码，ans是dp[l][r]的引用，修改它就会修改dp[l][r]
    int &ans = dp[l][r];
    
    // 如果已经计算过，直接返回结果（记忆化）
    if(ans != -1) return ans;
    
    // 初始化：设置为一个足够大的值，表示无穷大
    ans = 0x3f3f3f3f;   
    
    // 尝试所有可能的最后一次乘法位置
    for(int i = l + 1; i < r; i ++)
        // 状态转移：dp[l][r] = min(dp[l][i] + dp[i][r] + p[l]*p[i]*p[r])
        // 其中p[l]*p[i]*p[r]是最后一次乘法的代价
        ans = std::min(ans, DPS(l, i) + DPS(i, r) + p[l] * p[i] * p[r]);
    
    // 返回区间[l,r]的最优解
    return ans;
}

递推也可以写，分析计算顺序，大区间依赖小区间，那么按区间从小到大计算就可以写递推式DP了

// 初始化：单个矩阵不需要乘法，所以dp[i][i] = 0
for(int i = 1; i <= n; i ++)
    dp[i][i] = 0;

// 第一重循环：枚举子问题大小，从小到大处理子问题
// 从长度为2的区间开始，一直到长度为n的区间
for(int len = 2; len <= n; len ++) {
    // 第二重循环：枚举子问题的起点
    // 对于每个长度，计算所有可能的起点
    for(int l = 1; l <= n - len + 1; l ++) {
        // 计算子问题的终点
        int r = l + len - 1;
        
        // 初始化dp[l][r]为一种可能的方案：将第一个矩阵与剩余矩阵相乘
        dp[l][r] = dp[l + 1][r] + 1LL * p[l - 1] * p[l] * p[r];
        
        // 第三重循环：枚举最后一次矩阵乘法发生的位置
        // 尝试所有可能的切分点，找到最优解
        for(int i = l + 1; i < r; i ++)
            // 状态转移：dp[l][r] = min(dp[l][i] + dp[i+1][r] + p[l-1]*p[i]*p[r])
            // 其中p[l-1]*p[i]*p[r]是最后一次乘法的代价
            dp[l][r] = std::min(
                dp[l][r], 
                dp[l][i] + dp[i + 1][r] + p[l - 1] * p[i] * p[r]
            );
    }
}

背包DP

例：完全背包

有\(n\)种物品，每种物品\(i \in [1,n]\)的重量\(w_i\)，价值\(v_i\)，数量不限。有一个背包可装总重不超过\(b\)的物品，求背包能装物品的最大总价值。

例：

\(n=4\)，\(b=10\)

\(v_1=1\)，\(v_2=3\)，\(v_3=6\)，\(v_4=9\)

\(w_1=2\)，\(w_2=3\)，\(w_3=4\)，\(w_4=7\)

最优子结构：

\(k\)：只考虑前\(k\)种物品
\(y\)：背包装物品总重限制到\(y\) (\(y \leq b\))
\(d(k,y)\)：前\(k\)种物品装入容量\(y\)的背包的最优解
\(d(k,y)\)只与\(d(k,y-w_k)\)和\(d(k-1,y)\)有关

状态转移方程：

\(d(k,y) = \max\{d(k,y-w_k)+v_k, d(k-1,y)\}\)

直接DP：

for(int k = 1; k <= n; k ++)
    for(int y = 0; y <= b; y ++) {
        dp[k][y] = dp[k - 1][y];  // 用前i-1种物品方案初始化前i种物品方案
        if(y >= w[k])
            dp[k][y] = std::max(dp[k][y - w[k]] + v[k], dp[k - 1][y]);
    }

\(dp[i-1][\ldots]\)只在计算\(dp[i][\ldots]\)时被用到，实际上并不需要二维数组。

滚动数组优化：

1
2
3

for(int k = 1; k <= n; k ++)
    for(int y = w[k]; y <= b; y ++)
        dp[y] = std::max(dp[y - w[k]] + v[k], dp[y]);

滚动数组：

重复在一个数组内计算不同信息，减少空间复杂度
确保未处理的信息不被覆盖

劣势：

丢失了过程信息，无法还原完整方案

例：01背包

有\(n\)个物品，每个物品\(i \in [1,n]\)的重量\(w_i\)，价值\(v_i\)（分别只有1个）。有一个背包可装总重不超过\(b\)的物品，求背包能装物品的最大总价值。

最优子结构：

\(k\)：只考虑前\(k\)种物品
\(y\)：背包装物品总重限制到\(y\) (\(y \leq b\))
\(d(k,y)\)：前\(k\)种物品装入容量\(y\)的背包的最优解
\(d(k,y)\)只与\(d(k-1,y-w_k)\)和\(d(k-1,y)\)有关

状态转移方程：

\(d(k,y) = \max\{d(k-1,y-w_k)+v_k, d(k-1,y)\}\)

1
2
3

for(int k = 1; k <= n; k ++)
    for(int y = b; y >= w[k]; y --)
        dp[y] = std::max(dp[y - w[k]] + v[k], dp[y]);

其他背包问题：

多重背包：每种物品有\(k_i\)个
混合背包：有的1个，有的无限个，有的\(k_i\)个
二维背包：每个物品占\(w_i\)重量和\(a_i\)体积，重量体积都有上限

背包是一类多阶段决策问题：每做一次决策就可以得到解的一部分。

经典资料参考：背包九讲

线性结构DP

例：最长上升子序列

给定\(n\)个整数\(A_1,A_2,\ldots,A_n\)，找出最长的递增子序列。

例：1 5 3 6 9 8 10

最长上升子序列为：1<3<6<9<10

最优子结构：

\(d(k)\)：以第\(k\)个元素结尾的最长上升子序列长度
\(d(k)\)与\(i<k\)的每个\(d(i)\)有关
对任意\(i<k\)，如果\(A_i<A_k\)，则\(A_k\)续在以\(A_i\)结尾的子序列的后面

状态转移方程：

\(d(k) = \max\{d(i) | i<k \text{且} A_i<A_k\} + 1\)

int ans = 0;
for(int k = 1; k <= n; k ++) {
    dp[k] = 1;  // 至少自身有1的长度
    for(int j = 1; j < k; j ++)
        if(a[j] < a[k] && dp[j] + 1 > dp[k])
            dp[k] = dp[j] + 1;
    ans = std::max(dp[k], ans);
}

优化：

另存一个"尾元素"序列，表示各长度子序列的末尾元素
从左到右对每个数\(X\)在尾元素序列中二分查找不小于\(X\)的第一个\(Y\)
如果找到：用\(X\)替换\(Y\)，即该长度的子序列找到了更小的末尾元素
如果找不到：把\(X\)插入尾元素序列末尾，答案增长

int tlen = 0;   // 尾元素个数，指向尾元素数组最后一个元素的下一个位置
for(int i = 0; i < n; i ++) {
    int ith = std::upper_bound(b, b + tlen, a[i]) - b;  // 找到不小于a[i]的第一个数
    b[ith] = a[i];              // 用a[i]替换找到的位置，没找到则ith就是末尾位置
    if(ith == tlen) tlen ++;    // 没有不小于a[i]的数，长度增加
}

例：最长公共子序列

给两个序列\(A\)和\(B\)，求长度最大的公共子序列。

例：

\(A\)序列：1,3,2,8,6,5,7
\(B\)序列：2,1,4,8,5,7,9

最长公共子序列长度是4，即2,8,5,7

最优子结构：

\(d(i,j)\)：\(A\)的前\(i\)个元素与\(B\)的前\(j\)个元素的LCS
与\(d(i-1,j-1)\)、\(d(i,j-1)\)、\(d(i-1,j)\)有关：考察\(A_i\)与\(B_j\)是否相等
如果\(A_i=B_j\)，\(A_i\)与\(B_j\)配对一定可以作为\(d(i,j)\)的一个解的结尾
如果\(A_i \neq B_j\)，那么\(d(i,j)\)的解一定是\(d(i-1,j)\)和\(d(i,j-1)\)的其中一个

状态转移方程：

\(d(i,j) = \begin{cases} d(i-1,j-1)+1 & \text{若}A_i=B_j \\ \max(d(i,j-1), d(i-1,j)) & \text{若}A_i \neq B_j \end{cases}\)

int LCS(char a[], int alen, char b[], int blen) {
    dp[0][0] = dp[0][1] = dp[1][0] = 0;     // 假设a、b下标从1开始
    for(int i = 1; i <= alen; i ++) {       // a的游标
        for(int j = 1; j <= blen; j ++) {   // b的游标
            if(a[i] == b[j]) {
                // a[i] == b[j]时，加入a的前i-1、b的前j-1的LCS
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // a[i] != b[j]时，从另外两个子问题较大的转移
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[alen][blen];
}

其它DP前瞻

状态压缩DP

将子问题当作"状态"，状态转移方程就是状态的变化。把描述子问题的"状态"压缩为一个整数，优化状态转移效率。

例题：互不侵犯

\(N \times N\)的棋盘放置\(K\)个国王，国王攻击范围为周围8个格子。多少种摆放方案，能够互相不在攻击范围。

\(d(i,j,l)\)：前\(i\)行，第\(i\)行状态为\(j\)，已放置\(l\)个国王的方案数。 \(j\)就是压缩的状态：0~8格子有/没有国王是一个01串，用\(int\)表示。

状态压缩示意图（\(j=41_{(10)} = 101001_{(2)}\)）：

+---+---+---+---+---+---+
| 1 | 0 | 1 | 0 | 0 | 1 |
+---+---+---+---+---+---+
| K |   | K |   |   | K |
+---+---+---+---+---+---+

其中K表示放置国王，空格表示不放置国王。这个二进制数101001表示在第1、3、6列放置国王。

数位DP

统计满足一定条件的数的数量，把数字拆解一位一位地用DP处理。

例题：数字计数

给定两个正整数\(a,b\)，求\([a,b]\)范围内各数位0~9各出现多少次。

假设\(d(i)\)统计"1"出现的次数（0~9次数都相等）： \(d(i) = d(i-1) \times 10 + 10^{i-1}\)，然后做进一步作后续处理……

树形DP

在树结构上DP。

例题：树上的最远点对

\(n\)个结点的树，找两个点，它们的距离最远。

\(d(i)\)：节点\(i\)的子树中根到叶子的最大距离。 \(d(i) = \max\{d(j)\} + 1\)，\(j\)为\(i\)的子节点。所有\(d(j)\)最大的\(j=u\)和\(j=v\)，\(d(u)+d(v)+2\)为答案。

轮廓线DP（插头DP）

轮廓线DP是一种处理网格类问题的动态规划方法，特别适用于需要记录连通性信息的场景。其核心思想是沿着网格的轮廓线进行状态转移，通过记录轮廓线上每个格子的"插头"状态（如是否有路径经过、路径的方向等）来压缩状态空间。插头DP常用于解决哈密顿回路、路径覆盖、连通性等问题，如"回路计数"、"棋盘覆盖"等经典问题。通过巧妙的状态设计和转移规则，插头DP能够高效处理看似复杂的状态转移，是解决特定类型网格问题的重要工具。