动态规划

很多同学第一次接触动态规划，不理解它”动态”在哪、“规划”在哪。

实际上，它有一些”事后诸葛亮”的意思。例如，随着时间的推进，在面对不同的选择时，搜索算法会把所有的可能性都尝试一遍，贪心会短视地选择现在看来最好的那个，而动态规划则是：我不真正地去尝试所有的可能性，但也不抹杀任何可能性，而是把所有可能性用”状态”编码、记录下来，等到未来的事情发生以后，在新的局势之下，再来看当初选哪个更好。这种看到未来再重选过去的过程，就是其”动态”和”规划”的体现。

动态规划的思想允许我们找到最优解（而贪心往往只能找到次优解），同时其”状态”的设计又能避免花费像搜索那样的指数级时间代价。

定义#

动态规划（Dynamic Programming, DP） 是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

原理#

能使用动态规划求解的问题需要满足三个条件：最优子结构、无后效性、子问题重叠性。

最优子结构：大问题的最优解一定包含小问题的最优解，而不可能包含小问题的次优解。贪心算法也要求问题满足最优子结构。更多关于最优子结构的阐述，详见P1064 金明的预算方案 ↗。
无后效性：对于已经得到答案的子问题，不会因为后续决策改变答案。
子问题重叠：动态规划的子问题往往可以转移到多个大问题，或者说许多大问题的子问题是重叠的，此时花费一定空间去存储子问题的答案，可以节省重复计算子问题的时间。

以一个例子理解这些性质：

假设你需要从城市 A 途径城市 B~Y 前往城市 Z，相邻两个城市之间开设很多铁路车次，每个车次有票价和耗时两个参数。请问「在花费不超过给定值 $W$ 的情况下，你最快可以多久到达目的地？」

上述大问题可以拆成很多小问题：「从城市 A 到城市 B 的最短时间」、「从城市 A 到城市 C 的最短时间」……，并且后面子问题的最优解一定是从前面子问题的最优解组合出来的，因此满足最优子结构。

但是，由于有花费的限制，这种子问题划分是不符合无后效性的。试想你在前面几站花费过多，导致后面只能买慢车或者买不起车票，此时你不得不去改变前面几站的选择，破坏了无后效性。或者说，你在前面做出的选择，永远需要担心会不会在未来被回旋镖击中，必须修改。

因此我们需要重新把子问题划分得更细：「从城市 A 到城市 B 且花费不超过 $w$ 的最短时间」、「从城市 A 到城市 C 且花费不超过 $w$ 的最短时间」……

重新划分过后的子问题就满足无后效性了。因为通过把花费明确编码到状态里，你现在只需要选择那些在允许范围内的子问题即可，而不必担心可能会被迫修改前面的子问题的解。

通常有两种看法：

①最优子结构和无后效性是独立的，必须分别满足；
②最优子结构蕴含无后效性，满足前者则后者自动满足。

这取决于如何定义子问题和状态。

如果认为子问题的划分是问题本身”内蕴”的，与如何设计状态无关，那么最优子结构就是问题本身的性质，而无后效性是状态设计需要满足的条件，二者独立，必须分别满足；

如果认为子问题的划分和状态设计是绑定的，如何设计状态就代表了如何划分子问题，状态和子问题是一一对应的，那么只要状态设计不满足无后效性，子问题划分就不满足最优子结构，也即 $\neg \text{无后效性} \rightarrow \neg \text{最优子结构} \Leftrightarrow \text{最优子结构} \rightarrow \text{无后效性}$ .

动态规划一般采用递推的方式进行，直接从小问题的答案（边界）开始，不断组合成大问题的答案。当然也可以采用递归的方式先拆分再求解最后合并，这种方法称为「记忆化搜索」。

广义的动态规划可能代指一切递推算法，而不仅限于优化问题的算法。

应用#

背包问题（Knapsack）#

这是一个伪多项式时间的解法，详见计算理论#补充 ↗。

0-1 背包#

有 $n$ 件物品和一个容量为 $W$ 的背包。第 $i$ 件物品的重量为 $w_i$ ，价值为 $v_i$ . 每件物品只能选择放入或不放入（不可分割），求在不超过背包容量的情况下，能获得的最大价值。

状态设计：定义 dp[i][j] 表示只考虑前 $i$ 件物品、背包容量不超过 $j$ 时能获得的最大价值。

为什么要把「费用」（背包容量）也编码到状态里？回到上面的三个条件：

最优子结构：前 $i$ 件物品在容量 $j$ 下的最优解，要么包含第 $i$ 件（那么剩余部分就是前 $i-1$ 件在容量 $j-w_i$ 下的最优解），要么不包含第 $i$ 件（那就是前 $i-1$ 件在容量 $j$ 下的最优解）。大问题的最优解一定由小问题的最优解组合而来。
无后效性：如果不把容量编码到状态里，只记 dp[i] 为前 $i$ 件的最大价值，那么后面做决策时就无法知道还剩多少容量，不得不回头修改前面的选择，破坏了无后效性。把容量明确编码进去，就保证了后续决策不会改变已有子问题的答案。
子问题重叠：不同的物品选择序列可能到达同一个 (i, j) 状态，存储 dp[i][j] 就避免了重复计算。

状态转移方程：

dp[i][j] = \max(dp[i-1][j],\ dp[i-1][j-w_i] + v_i)

其中第二项仅在 $j \geq w_i$ 时有效。边界：dp[0][j] = 0.

空间优化：注意到 dp[i][...] 只依赖 dp[i-1][...]，可以用滚动数组压缩为一维：dp[j] 表示容量不超过 $j$ 时的最大价值。但需要注意：内层枚举 $j$ 时必须从大到小，否则同一件物品会被重复使用（那就变成完全背包了）。

C++
Python

int dp[W_MAX + 1] = {0};
for (int i = 1; i <= n; i++)
    for (int j = W; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

cpp

dp = [0] * (W_MAX + 1)
for i in range(1, n + 1):
    for j in range(W, w[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])

python

时间复杂度： $O(nW)$
空间复杂度： $O(W)$ （滚动数组优化后）

完全背包#

有 $n$ 件物品和一个容量为 $W$ 的背包。第 $i$ 件物品的重量为 $w_i$ ，价值为 $v_i$ . 每种物品有无限件，可以选任意件数，求在不超过背包容量的情况下，能获得的最大价值。

和 0-1 背包的区别在于同一件物品可以选多次，因此状态转移时需要考虑「选 $k$ 件第 $i$ 件物品」的所有可能。朴素的三维枚举是：

dp[i][j] = \max_{0 \leq k \cdot w_i \leq j}(dp[i-1][j-k \cdot w_i] + k \cdot v_i)

但可以发现 $dp[i][j - w_i]$ 其实已经包含了「在前 $i$ 件物品中选、容量 $j-w_i$ 下的最优解」，它可能已经用了若干件第 $i$ 件物品。因此可以直接写成：

dp[i][j] = \max(dp[i-1][j],\ dp[i][j-w_i] + v_i)

注意第二项依赖的是 dp[i][...]（同一行）而非 dp[i-1][...]. 在一维滚动数组下，这恰好意味着内层 $j$ 必须正序枚举——和 0-1 背包刚好相反。

C++
Python

int dp[W_MAX + 1] = {0};
for (int i = 1; i <= n; i++)
    for (int j = w[i]; j <= W; j++)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

cpp

dp = [0] * (W_MAX + 1)
for i in range(1, n + 1):
    for j in range(w[i], W + 1):
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])

python

时间复杂度： $O(nW)$
空间复杂度： $O(W)$

除了 0-1 背包和完全背包，背包问题还有很多变种，比如多重背包、多维费用背包、分组背包。这些背包问题可以参考背包九讲 ↗。

最大子串和#

给定一个长度为 $n$ 的整数数列 $a_1, a_2, \ldots, a_n$ （可能含负数），求一个连续子串 $a_i, \ldots, a_j$ ，使得其和最大。

状态设计：dp[i] 表示以位置 $i$ 结尾的所有连续子串中的最大和。为什么要以「结尾」而不是「前 $i$ 个中最大的」？因为子串要求连续，只有固定了结尾，才能明确地决定 $a_{i+1}$ 是接上去还是另起一段。

状态转移：对于 $a_{i+1}$ ，要么接到以 $i$ 结尾的最优子串后面（dp[i] + a[i+1]），要么自己单独开始一段（a[i+1]）。取较大者：

dp[i] = \max(dp[i-1] + a_i,\ a_i)

最终答案就是所有 dp[i] 中的最大值。

C++
Python

int dp = a[1], ans = a[1];
for (int i = 2; i <= n; i++) {
    dp = max(dp + a[i], a[i]);
    ans = max(ans, dp);
}

cpp

dp = ans = a[0]
for i in range(1, n):
    dp = max(dp + a[i], a[i])
    ans = max(ans, dp)

python

时间复杂度： $O(n)$
空间复杂度： $O(1)$ （只保留当前 dp 和全局 ans）

最大子串和的引申

有最大长度限制的最大子串和：要求子串长度不超过 $K$ .

思路：记前缀和 $S_i = a_1 + \cdots + a_i$ ，则子串 $a_{j+1 \ldots i}$ 的和为 $S_i - S_j$ . 固定右端点 $i$ ，要在满足 $i - j \leq K$ 的范围内找到最小的 $S_j$ ，即维护一个长度不超过 $K$ 的滑动窗口中的前缀和最小值。用单调队列可以在 $O(n)$ 时间内完成。

环形数列的最大子串和：数列首尾相接，允许子串跨越边界。两种做法：

复制拼接：把数列复制一份拼在后面，得到 $a_1, \ldots, a_n, a_1, \ldots, a_n$ ，然后在长度为 $2n$ 的数列上做有最大长度限制（不超过 $n$ ）的方法。
总和减最小子串和：环形情况下的最大子串和要么不跨越边界（就是普通的最大子串和），要么跨越边界（此时中间没被选中的部分就是最小子串和）。所以答案 = $\max($ 普通最大子串和 $,\ \text{总和} -$ 普通最小子串和 $)$ . 注意全为负数时需要特殊处理。

最长上升子序列（Longest Increasing Sub-sequence, LIS）#

给定一个长度为 $n$ 的序列 $a_1, \ldots, a_n$ ，求最长的严格递增子序列的长度（子序列不要求连续，但相对顺序不能变）。

$O(n^2)$ DP 解法：

dp[i] 表示以位置 $i$ 结尾的最长上升子序列的长度。要计算 dp[i]，枚举所有 $j < i$ ，如果 $a_j < a_i$ 就可以把 $a_i$ 接在以 $j$ 结尾的上升子序列后面：

dp[i] = \max_{j < i,\ a_j < a_i}(dp[j] + 1)

C++
Python

int dp[N], ans = 0;
for (int i = 1; i <= n; i++) {
    dp[i] = 1;
    for (int j = 1; j < i; j++)
        if (a[j] < a[i])
            dp[i] = max(dp[i], dp[j] + 1);
    ans = max(ans, dp[i]);
}

cpp

dp = [1] * n
for i in range(n):
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
ans = max(dp)

python

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

贪心 + 二分优化到 $O(n \log n)$ ：

上面的 DP 之所以慢，是因为每个 dp[i] 都要扫描前面所有位置。我们可以换一种状态定义：tail[k] 表示所有长度为 $k+1$ 的上升子序列中，结尾元素的最小值。关键观察：tail 数组一定是严格递增的——如果长度为 $3$ 的上升子序列能以 $x$ 结尾，那么截掉最后一个元素，长度为 $2$ 的上升子序列一定能以比 $x$ 小的数结尾，所以 tail[1] < tail[2].

有了单调性，就可以用二分查找定位：对于每个新元素 $x$ ，在 tail 中找到第一个 $\geq x$ 的位置并替换（这样可以在不破坏递增的前提下，让对应长度的子序列结尾更小）；如果所有元素都 $< x$ ，则 $x$ 可以接在最后面，LIS 长度加一。

flowchart TD
    A[遍历序列中的每个元素 x] --> B{tail 中存在 ≥ x 的元素?}
    B -->|是| C[找到第一个 ≥ x 的位置，替换为 x]
    B -->|否| D[x 追加到 tail 末尾，长度 +1]
    C --> E[继续下一个元素]
    D --> E

C++
Python

int tail[N], len = 0;
for (int i = 1; i <= n; i++) {
    int pos = lower_bound(tail, tail + len, a[i]) - tail;
    tail[pos] = a[i];
    if (pos == len) len++;
}

cpp

from bisect import bisect_left

tail = []
for x in a:
    pos = bisect_left(tail, x)
    if pos == len(tail):
        tail.append(x)
    else:
        tail[pos] = x
ans = len(tail)

python

时间复杂度： $O(n \log n)$
空间复杂度： $O(n)$

最长公共子序列（Longest Common Sub-sequence, LCS）#

给定两个序列 $A = a_1, \ldots, a_n$ 和 $B = b_1, \ldots, b_m$ ，求它们的最长公共子序列的长度。

状态设计：dp[i][j] 表示 $A$ 的前 $i$ 个元素和 $B$ 的前 $j$ 个元素的 LCS 长度。和编辑距离类似，双串问题常常把两个串的长度作为状态的两个维度。

状态转移：

如果 $a_i = b_j$ ，那么这对字符一定可以匹配：dp[i][j] = dp[i-1][j-1] + 1
如果 $a_i \neq b_j$ ，则要么跳过 $a_i$ ，要么跳过 $b_j$ ，取较优者：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

C++
Python

int dp[N][M] = {0};
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i] == b[j])
            dp[i][j] = dp[i-1][j-1] + 1;
        else
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

cpp

dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

python

时间复杂度： $O(nm)$
空间复杂度： $O(nm)$ （同样可以用滚动数组优化到 $O(\min(n, m))$ ）

当每个元素只出现一次时：LCS → LIS 转化

如果两个序列中的每个元素在各自序列中最多出现一次，可以把 LCS 转化为 LIS 来求解，从而将复杂度从 $O(nm)$ 降到 $O(\min(n, m) \log(\min(n,m)))$ .

做法：

记录序列 $A$ 中每个元素出现的位置 pos[a_i]
遍历序列 $B$ ，对于 $B$ 中的每个元素 $b_j$ ，如果它也在 $A$ 中出现，就把 pos[b_j] 加入一个新序列 $C$
对 $C$ 求 LIS，其长度就是原 LCS 的长度

为什么这样是对的？ LCS 要求找到的公共元素在两个序列中的相对顺序一致。转化后， $C$ 中的每个数代表 $A$ 中的某个位置索引，对 $C$ 求 LIS 就是在找一个索引递增的子序列——这等价于公共元素在 $A$ 中顺序出现。而它们本身来自 $B$ 的扫描，所以在 $B$ 中也是顺序出现的。

当 $n, m$ 较大且元素只出现一次时，这个方法比朴素的二维 DP 更快（尤其是配合 $O(n \log n)$ 的 LIS 算法）。

题目#

编辑距离#

题目：P2758 编辑距离 ↗。

设 $A$ 和 $B$ 是两个字符串。我们要用最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$ . 操作有三种：删除一个字符、插入一个字符、将一个字符改为另一个字符。 $A, B$ 均只包含小写字母，长度均不超过 $2000$ .

状态设计：这是一个典型的双串 DP。定义 dp[i][j] 表示将 $A$ 的前 $i$ 个字符转换为 $B$ 的前 $j$ 个字符所需的最少操作次数。和 LCS 一样，把两个串的长度各作为一个维度，是因为我们需要同时跟踪两个串的匹配进度。

边界：

dp[0][0] = 0：空串变空串不需要操作
dp[i][0] = i：把 $A$ 的前 $i$ 个字符全部删除
dp[0][j] = j：向空串中插入 $B$ 的前 $j$ 个字符

状态转移：考虑 dp[i][j]，最后一步操作一定是以下三种之一：

删除：先把 $A[1\ldots i-1]$ 变成 $B[1\ldots j]$ （花费 dp[i-1][j]），再删除 $A[i]$ . 花费 dp[i-1][j] + 1.
插入：先把 $A[1\ldots i]$ 变成 $B[1\ldots j-1]$ （花费 dp[i][j-1]），再在末尾插入 $B[j]$ . 花费 dp[i][j-1] + 1.
替换：先把 $A[1\ldots i-1]$ 变成 $B[1\ldots j-1]$ （花费 dp[i-1][j-1]），然后如果 $A[i] = B[j]$ 就不操作，否则替换 $A[i]$ 为 $B[j]$ . 花费 dp[i-1][j-1] + (A[i] == B[j] ? 0 : 1).

三者取最小值即可。

dp[i][j] = \min \begin{cases} dp[i-1][j] + 1 & \text{（删除）}\\ dp[i][j-1] + 1 & \text{（插入）}\\ dp[i-1][j-1] + [A_i \neq B_j] & \text{（替换 / 匹配）} \end{cases}

C++
Python

int dp[N][M];
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
        int cost = (a[i] == b[j] ? 0 : 1);
        dp[i][j] = min({
            dp[i-1][j] + 1,       // 删除
            dp[i][j-1] + 1,       // 插入
            dp[i-1][j-1] + cost   // 替换
        });
    }

cpp

dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = i
for j in range(m + 1):
    dp[0][j] = j
for i in range(1, n + 1):
    for j in range(1, m + 1):
        cost = 0 if a[i-1] == b[j-1] else 1
        dp[i][j] = min(
            dp[i-1][j] + 1,       # 删除
            dp[i][j-1] + 1,       # 插入
            dp[i-1][j-1] + cost   # 替换
        )

python

graph TD
    A["dp[i-1][j]"] -->|"删除 +1"| D["dp[i][j]"]
    B["dp[i][j-1]"] -->|"插入 +1"| D
    C["dp[i-1][j-1]"] -->|"替换 +1 / 匹配 "| D

时间复杂度： $O(|A| \cdot |B|)$ ，两层循环遍历整个 DP 表
空间复杂度： $O(|A| \cdot |B|)$ （可以用滚动数组优化到 $O(\min(|A|, |B|))$ ）

定义#

原理#

应用#

背包问题（Knapsack）#

0-1 背包#

完全背包#

最大子串和#

最长上升子序列（Longest Increasing Sub-sequence, LIS）#

最长公共子序列（Longest Common Sub-sequence, LCS）#

题目#

编辑距离#

更多#