动态规划是一种解决多阶段决策优化问题的高效算法策略，核心思想是通过将复杂问题分解为相互关联的子问题，利用子问题的解构建全局的最优解。

多阶段决策优化问题将复杂问题按时间或空间特征分解为若干相互关联的阶段，每个阶段都需要做出决策，且当前阶段的决策会影响后续阶段的状态和选择，最终通过递推求解整个问题的最优策略。

它的核心在于通过分阶段决策和状态转移实现全局最优，而非仅局部最优。

算法概念

核心特征

动态规划适用于具有以下两个核心特征的问题：

• 最优子结构：问题的最优解包含其子问题的最优解。也就是说，大问题的最优答案可以由小问题的最优答案组合而来。

例如，从北京坐高铁到广州，最优路线如果经过武汉，那么"北京→武汉"这一段一定也是最优路线，“武汉→广州"那一段也是最优路线。

反例：最长简单路径问题（不允许重复经过同一顶点）就不具有最优子结构——局部最优拼起来不一定是全局最优。

• 重叠子问题：在递归求解过程中，同一个子问题会被反复计算多次。

例如：计算斐波那契数列 $F(5) = F(4) + F(3)$，其中 $F(4) = F(3) + F(2)$，$F(3)$ 被算了两次。

如果子问题不重叠（如分治法中的归并排序），那就不需要 DP，直接分治即可。

贪心与动态规划

相同点：

• 两者都通过将大问题分解为小问题，然后逐步解决这些小问题来找到大问题的答案。
• 两者都依赖问题的最优子结构性质，一个问题的最优解包含其子问题的最优解。

不同点：

总的来说，贪心法和动态规划都有各自的适用场景，选择哪一种方法取决于具体的问题特性。

动态规划的原理

动态规划是一种在各个不同大小的子问题的优化值之间建立递归关系并求解的过程。

利用优化原理，使用枚举法建立不同长度子问题的优化值之间的递归关系：状态转移方程。

基本步骤

实现方式

动态规划的两种实现方式：

应用

多段图

多段图是一种分层有向图，顶点集被划分为 $k$ 个互不相交的段（阶段） $V_1, V_2, \cdots, V_k$，其中：

• 源点 $s$ 位于第1段 $V_1$，汇点 $t$ 位于最后一段 $V_k$。
• 边仅存在于相邻的段之间（即从 $V_i$ 的顶点到 $V_{i+1}$ 的顶点），不允许跨段或回退（即不存在环）。

现要寻找从源点 $s$ 到汇点 $t$ 的最短路径。

多段图问题满足优化原理：最短路径上的子路径也是该两点之间的最短路径。

• 最短路 $(1 \rightarrow 3 \rightarrow 5 \rightarrow 7)$ 上的子路径 $(3 \rightarrow 5 \rightarrow 7)$ 是3到目的节点7在子图上的最短路径。
• 无论最短路的下一跳是 $\{2,3,4\}$ 中的哪个节点，其后的路径也应是最短路径。
• 节点1到目的节点的最短路长度 $c(1)$ 可从 $\{2,3,4\}$ 到目的节点的最短长度 $c(j)$ 加上 节点1到这些节点的边成本 $\text{cost}(1,j)$ 经过枚举得到： $$c(1) = \min_{j \in \{2,3,4\}} \{c(j) + \text{cost}(1,j)\}$$

一般情形：设 $c(i)$ 为 $i$ 到目的节点的最短路长度，$A(i)$ 为与 $i$ 相邻的结点集合，则有状态转移方程

因此，对于上图，存在以下递推关系：

故最短路径长度为 $7$。

0/1背包

虽然不知道优化解是否放物品1，但我们可以利用优化原理，从枚举“放”和“不放”两种情形建立递归式

设 $f(i,y)$ 为以背包容量 $y$ 放物品 $i,…,n$ 得到的优化效益值，以下递归关系成立：

例如，对于 $n=3$，$w=[100,14,10]$，$p=[20,18,15]$，$c=116$ 的0/1背包问题，

• 若放进物品1 $(x_1=1)$，背包容量还剩 $r=16$。此时 $[x_2, x_3]=[1,0]$ 为子问题的优化解，值为18。
• 若不放物品1 $(x_1=0)$，则对剩下物品而言，容量限制仍然为116，则子问题的优化解为 $[1,1]$，值为33。

前者总效益为38，后者为33。所以优化解为 $[1,1,0]$，优化值为38。

令 $f(i,y)$ 表示容量为 $y$，物品 $i, i+1, \cdots, n$ 的优化效益值，按优化原理可列递归关系式如下：

第2行表示背包容量 $y$ 不足以放下物品 $i$。

0/1背包问题的3种动态规划实现方法：

递归实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int w[n];
int p[n];

int knapsack(int i, int y) {
    // 尝试最后一个物品
    if (i == n) return (y < w[n]) ? 0 : p[n];
    // 剩余容量不足以装入物品i，跳过该物品
    if (y < w[i]) return knapsack(i+1, y);
    // 状态转移方程
    return max(knapsack(i+1, y), knapsack(i+1, y-w[i])+p[i]);
}

递归方程

其中 $a,b$ 为常数，则有 $T(n) = \Theta(2^n)$。

迭代实现

当物品重量为整数时，可设计一个相当简单的算法求解 $f(1,c)$。该方法用 $\Theta(cn)$ 大小的二维数组 f[i][y] 来保存每个 $f(i,y)$ 的值，并且只计算一次。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

void knapsack(int p[], int w[], int c, int n, int f**) {
    for (int y=0; y<=w[n]; y++) {
        f[n][y] = 0;
    }
    for (int y=w[n]; y<=c; y++) {
        f[n][y] = p[n];
    }
    for (int i=n-1; i>1; i--) {
        for (int y=0; y<=w[i]; y++) {
            f[i][y] = f[i+1][y];
        }
        for (int y=w[i]; y<=c; y++) {
            f[i][y] = max(f[i+1][y], f[i+1][y-w[i]]+p[i]);
        }
        f[1][c] = f[2][c];
        if (c>w[1]) {
            f[1][c] = max(f[1][c], f[2][c-w[1]]+p[1]);
        }
    }
}

或者自底向上：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int dp[MAX_N][MAX_W] = {0};

void knapsack() {
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= c; w++) {
            if (w[i-1] <= w) {
                // 选或不选取最大值
                int not_take = dp[i-1][w];
                int take = dp[i-1][w - w[i-1]] + p[i-1];
                dp[i][w] = max(not_take, take);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
}

元组法实现

迭代实现有两个缺点:

• 要求物品重量必须为整数；
• 当背包容量 $c$ 很大时空间复杂度剧增（例如当 $c>2n$ 时所需存储空间猛涨为 $\Theta(n2^n)$）。

元组法将函数 $f(i, y)$ 的跳跃点以元组 $(y, f(i, y))$ 形式存储于一个线性表 $P(i)$ 中。表 $P(i)$ 中的元组 $(y,f(i, y))$ 按 $y$ 的增序排列。

$P(i)$ 中的元组 $(a,b)$ 表示：存在一种装物品 $\{i,i+1,\cdots,n\}$ 的方案，能在容量 $y$（$a \leqslant y<a'$，$a'$ 为下一元组的横坐标）的条件下得到效益值 $b$。

📝 备注

核心思想就是维护一个集合 $S^i$，里面放的是“考虑了前 $i$ 个物品后，所有可能达到的（重量, 价值）组合”。

但不可能存下所有组合，关键技巧是支配规则：如果组合 $A$ 的重量比组合 $B$ 重，但价值反而比组合 $B$ 低（或一样），那 $A$ 永远不如 $B$。即 $A$ 被 $B$ 支配了，可以扔掉。

下面给出从 $f(i+1,y)$ 的线性表 $P(i+1)$ 得出 $f(i,y)$ 的线性表 $P(i)$ 的算法：

• 按照 $f(i,y)$ 的定义: $$f(i,y)=\max\{f(i+1,y),f(i+1,y-w_i)+p_i\}$$首先需要从 $P(i+1)$ 得到函数 $$f^*(i+1,y)=f(i+1,y-w_i)+p_i$$的元组集合 $Q$。
• 设 $(a,b)\in Q$，则 $(a-w_i, b-p_i) \in P(i+1)$，反之亦然。所以，$P(i+1)$ 的每个元组 $(w,p)$ 对应 $Q$ 的一个元组 $(w+w_i, p+p_i)$。

$Q$ 的元组 $(u,v)$ 代表装物品 $\{i,i+1, \cdots ,n\}$ 的一种方案：以背包容量 $u$ 得到效益值 $v$。

• 再从 $P(i+1)$ 和 $Q$ 得到 $f(i,y)$ 的元组（即 $P(i)$ 的元组）。因 $P(i+1)$ 和 $Q$ 内元组均按 $w$ 和 $p$ 的增序排列，所以可进行合并。合并时使用以下支配规则：
  • 设 $(a,b)$ 和 $(u,v)$ 是来自 $P(i+1)$ 和 $Q$ 的元组，若 $a\geqslant u$且 $b<v$，则称 $(a,b)$ 受 $(u,v)$ 支配，

因为 $(a,b)$ 代表以容量 $a$ 得到效益值 $b$ 的方案，而 $(u,v)$ 代表以较少的容量 $u$ 得到较大效益值 $v$ 的装包方案。

• 产生 $P(i)$ 时丢弃 $w>c$ 的元组 $(w,v)$。
• 得到 $P(2)$ 后不再产生 $P(1)$：
  • $P(2)$ 的最后一个元组是 $f(2,c)$ 对应的元组；
  • 设线性表 $P(2)$ 中满足 $w+w_1 \leqslant c$ 的最后一个元组为 $(w,v)$，将 $v+p_1$ 与 $P(2)$ 的最后一个元组对应的效益值 $p$ 做比较，效益值大的即为优化效益值 $f(1,c)$。

案例：设 $n=5$，$c=10$，$w=[2,2,6,5,4]$，$p=[6,3,5,4,6]$。求 $f(1,10)$。

• 易知 $$P(5)=[(0,0), (4,6)]$$
• 欲求 $P(4)$，先加 $(5,4)$ 求出 $Q=[(5,4),(9,10)]$。$(5,4)$ 方案的效益值不如 $(4,6)$ 代表的方案好，合并舍弃 $(5,4)$ 得 $$P(4)=[(0,0),(4,6),(9,10)]$$
• 再加上 $(6,5)$ 得 $Q=[(6,5),(10,11)]$ 合并得 $P(3)$。此时舍弃了 $(15,15)$，因为15超过了背包容量。合并 $P(4)$ 和 $Q$ 得 $$P(3)=[(0,0),(4,6),(9,10),(10,11)]$$
• 继续加 $(2,3)$ 得到 $Q=[(2,3),(6,9)]$，合并舍弃得 $$P(2)=[(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)]$$
• 最后，$P(2)$ 中还能放下物品1 $(2,6)$ 的最大效益组合为 $(6,9)$。而 $(2,6)+(6,9)=(8,15)$ 优于 $(10,11)$，所以最优效益值为15。

该算法最坏情形的时间复杂度为 $\mathrm{O}(2^n)$。

$P(i)$ 中的元组个数至多为 $P(i+1)$ 中元组个数的2倍。初始 $P(n)=2$，所以 $P(i)$ 中的元组个数不超过 $2^{n-i+1}$。

计算所有 $P(i)$ 时所需要的总时间为 $\mathrm{O}(2^n)$：

• 计算 $Q$：$\mathrm{O}(|P(i+1)|)$。
• 合并 $P(i+1)$ 和 $Q$：$\mathrm{O}(|P(i+1)|+|Q|)=\mathrm{O}(2|P(i+1)|)$。
• 因此计算 $P(i)$：$\mathrm{O}(2^{n-i+1})$。

最长连续子序列

已知数组 $a = [a_1, a_2, \cdots, a_n]$，求出它的最大子序列及该子序列中所有元素的和。

使用动态规划思想，从左到右遍历一遍，维护两个值：

• current：以当前位置结尾的最大子段和。
• max_sum：全局最大子段和。

然后，对于每个元素 $a_i$，如果 current + a[i] > a[i]，就加上 $a_i$ 继续延长；否则，从 $a_i$ 重新开始。

由此可得出状态转移方程为：

例如，对于数组 $a = [-1, -2, 3, -4, -5, 6, 7, 8, -9, 10]$，对应的最长连续子序列为 $x = [3, -4, -5, 6, 7, 8, -9, 10]$。

旅行商问题

旅行商问题（Travelling Salesman Problem，简称TSP）是计算数学中的一个经典问题。这个问题描述的是一个旅行商人从某个城市出发，经过一系列的城市，每个城市只能经过一次，最后回到原点，如何才能使得所经过的路程最短。

简化描述：给定一个图，寻找一条最短的环路，使得每个顶点恰好经过一次，并且最后回到原点。即求图 $G=(V,E)$ 的最小成本周游路线。

令 $S$ 为 $V$ 的不含节点1的子集，设 $g(i,S)$ 表示从节点 $i$ $(i \notin S)$ 出发，经过 $S$ 中所有节点各一次，到达节点1的最短路径长度，则有以下状态转移方程：

• 原问题为：$g(1, V-\{1\})$
• 初始状态：$g(i, \oslash) = c_{i,1}$
• 从 $S = \oslash$ 开始，依次对 $|S| = 1,2, \cdots, n-1$ 计算

算法的时间复杂度：

• $|S|=k$ 的子问题个数为 $\mathrm{C}_{n-2}^k$
• 在 $|S|=k$ 时，求最小值需做 $k-1$ 次比较

则算法的时间复杂度（比较次数）为

矩阵乘法链

$m \times n$ 矩阵 $\bm{A}$ 与 $n \times p$ 矩阵 $\bm{B}$ 相乘需要元素乘法 $m \cdot n \cdot p$ 次，

$(\bm{A} \times \bm{B}) \times \bm{C}$ 与 $\bm{A} \times (\bm{B} \times \bm{C})$ 的元素乘法次数不同。例如，假定 $\bm{A} \in \mathbb{R}^{100 \times 1}$，$\bm{B} \in \mathbb{R}^{1 \times 100}$，$\bm{C} \in \mathbb{R}^{100 \times 1}$，则：

• $(\bm{A} \times \bm{B}) \times \bm{C}$ 的乘法次数为 $1 \times 100 \times 100 + 100 \times 100 \times 1 = 20000$
• $\bm{A} \times (\bm{B} \times \bm{C})$ 的乘法次数为 $1 \times 100 \times 1 + 100 \times 1 \times 1 = 200$

问题：对任意给定长度 $q$ 的矩阵乘法链

求优化的乘法顺序使得计算该乘法链所用的乘法数最少

用 $M(i,j)$ 表示链 $M_i \times \cdots \times M_j$ 的乘积，假设优化的矩阵乘法链的顺序最后计算乘积 $M(i,k) \times M(k+1,j)$，则计算 $M(i,j)$ 的优化乘法顺序在计算子链 $M(i,k)$ 和 $M(k+1,j)$ 时也是优化的。

设 $c(i,j)$ 为计算 $M(i,j)$ 的优化乘法数（优化值），根据优化原理，优化值之间满足

All-Pair最短路径问题

设 $G$ 为有向图，其中每条边都有一个成本，图中每条有向路径。