动态规划算法(DP)
动态规划(Dynamic Programming,简称 DP)是一种通过保存子问题的计算结果,避免重复计算的算法思想。
对于一些可以分解成若干子问题的题目,如果直接使用递归,可能会反复计算相同的内容。动态规划则将已经计算出的结果保存下来,再利用这些结果求解后续问题。
动态规划主要需要考虑四个问题:
- 状态定义
- 状态转移方程
- 初始状态及边界条件
- 状态的计算顺序
其中最重要的是状态定义。例如 f[i] 或 f[i][j] 分别表示什么,必须先明确,才能继续考虑状态转移。
一、Fibonacci 数列
以 Fibonacci 数列为例:
当 $n\geq3$ 时:
直接使用递归:
int fib(int n) {
if (n <= 2)return 1;
return fib(n - 1) + fib(n - 2);
}
这种写法虽然简单,但是存在大量重复计算。例如求 fib(5) 时,计算 fib(4) 和 fib(3) 的过程中又会重复求解 fib(2)、fib(3) 等。
可以使用数组保存已经计算的结果。
定义 f[i] 表示 Fibonacci 数列第 $i$ 项的值,则状态转移方程为:
初始状态为:
代码实现:
#include <cstdio>
using namespace std;
int f[1000];
int main() {
int n;
scanf("%d", &n);
f[1] = f[2] = 1;
for (int i = 3; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
printf("%d\n", f[n]);
return 0;
}
这里每个状态只需要计算一次,时间复杂度为 $O(n)$,相比直接递归减少了重复计算。
二、状态与状态转移
动态规划通常使用数组保存状态。
例如:
f[i]:处理到第 $i$ 个位置时的最优结果。
f[i][j]:处理前 $i$ 个元素,并满足条件 $j$ 时的最优结果。
定义状态后,需要考虑当前状态可以由哪些已经计算完成的状态得到。
例如:
这里 f[i] 由前面的两个状态转移得到。
另外还需要确定初始状态。一般可以根据题意设置:
或者:
计算顺序也很重要,因为当前状态所依赖的前驱状态必须已经计算完成。有些 DP 可以直接从前向后递推,有些则需要倒序计算。
下面通过几种常见题型分析。
三、数字三角形
给出一个数字三角形:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
从顶部出发,每次只能走到下一行相邻的位置,要求经过数字的最大和。
使用二维数组 a[i][j] 存储三角形中的数字。
定义 f[i][j] 表示从顶部走到第 $i$ 行、第 $j$ 个位置时能够取得的最大数字和。
对于位置 $(i,j)$,只能从上一行的 $(i-1,j-1)$ 或 $(i-1,j)$ 转移过来。
因此:
需要注意三角形左右两侧的边界,最左边和最右边都只有一个前驱状态。
代码实现:
#include <cstdio>
#include <algorithm>
using namespace std;
int a[1005][1005], f[1005][1005];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
scanf("%d", &a[i][j]);
f[1][1] = a[1][1];
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (j == 1)
f[i][j] = f[i - 1][j] + a[i][j];
else if (j == i)
f[i][j] = f[i - 1][j - 1] + a[i][j];
else
f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
}
}
int ans = 0;
for (int j = 1; j <= n; j++)
ans = max(ans, f[n][j]);
printf("%d\n", ans);
return 0;
}
整个三角形共有:
个状态。
每个状态最多只需要比较两个前驱状态,因此时间复杂度为 $O(n^2)$。
四、01 背包
01 背包是动态规划中的常见问题。
有 $n$ 个物品,第 $i$ 个物品的重量为 $w[i]$,价值为 $v[i]$,背包的最大容量为 $m$。每件物品只能选择一次,要求在总重量不超过背包容量的情况下,使总价值最大。
定义:
f[i][j] 表示只考虑前 $i$ 个物品,背包容量为 $j$ 时能够取得的最大价值。
对于第 $i$ 个物品,有两种情况。
1. 不选择当前物品
2. 选择当前物品
必须满足 $j\geq w[i]$,则:
综合两种情况,可以得到状态转移方程:
当 $j\lt w[i]$ 时,只能选择不放入当前物品。
代码实现:
#include <cstdio>
#include <algorithm>
using namespace std;
int w[1005], v[1005];
int f[1005][1005];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &w[i], &v[i]);
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= w[i])
f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
}
}
printf("%d\n", f[n][m]);
return 0;
}
时间复杂度为 $O(nm)$,空间复杂度同样为 $O(nm)$。
01 背包的空间优化
观察状态转移方程可以发现,第 $i$ 行只依赖第 $i-1$ 行的数据,因此不需要保存全部的二维状态。
可以直接使用一维数组 f[j] 保存当前容量下的最优价值。
转移方程:
代码:
#include <cstdio>
#include <algorithm>
using namespace std;
int w[1005], v[1005];
int f[10005];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &w[i], &v[i]);
for (int i = 1; i <= n; i++)
for (int j = m; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);
printf("%d\n", f[m]);
return 0;
}
这里需要注意,01 背包的容量必须从大到小枚举。
假设当前物品重量为 2,价值为 3。如果从小到大枚举,先更新:
随后计算:
由于 f[2] 已经在当前一轮被更新,实际上相当于同一个物品被选择了两次。
而 01 背包中每个物品只能选择一次,因此必须倒序更新,保证本轮转移使用的仍然是上一轮的状态。
空间压缩后,时间复杂度仍然为 $O(nm)$,空间复杂度降低为 $O(m)$。
五、完全背包
完全背包与 01 背包类似,区别在于每种物品可以选择任意多次。
一维状态转移方程仍然是:
但是容量的遍历方向不同。
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= m; j++)
f[j] = max(f[j], f[j - w[i]] + v[i]);
完全背包需要从小到大枚举容量。
因为当前物品可以重复选择,因此允许使用本轮已经更新过的状态继续进行转移。
所以:
- 01 背包:容量从大到小枚举。
- 完全背包:容量从小到大枚举。
两者状态转移形式相同,但是由于物品的选择次数不同,遍历顺序也不同。
六、最长上升子序列(LIS)
最长上升子序列(Longest Increasing Subsequence,LIS)是另一类比较常见的动态规划问题。
给定一个数列:
3 1 2 5 4
要求从中选择若干个元素,使其严格递增,并且长度最大。
例如 1 2 5 或 1 2 4,长度均为 3。
定义 f[i] 表示以第 $i$ 个元素结尾的最长上升子序列长度。
对于所有 $j\lt i$,如果 $a[j]\lt a[i]$,就可以将 a[i] 接到以 a[j] 结尾的上升子序列之后。
状态转移为:
其中要求 $j\lt i$ 且 $a[j]\lt a[i]$。
由于每个元素自身也能构成长度为 1 的上升子序列,所以需要先将 f[i] 初始化为 1。
代码实现:
#include <cstdio>
#include <algorithm>
using namespace std;
int a[1005], f[1005];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int ans = 0;
for (int i = 1; i <= n; i++) {
f[i] = 1;
for (int j = 1; j < i; j++)
if (a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
ans = max(ans, f[i]);
}
printf("%d\n", ans);
return 0;
}
对于每个 $i$,都需要枚举前面所有可能的 $j$,因此时间复杂度为 $O(n^2)$。
LIS 还可以进一步优化,不过这里主要使用普通 DP 的方法求解。
七、记忆化搜索
动态规划除了从初始状态开始递推,也可以通过记忆化搜索实现。
记忆化搜索可以理解为在递归的基础上增加一个数组,用于保存已经计算过的状态。
还是以 Fibonacci 数列为例:
int f[1000];
int solve(int n) {
if (n <= 2)return 1;
if (f[n] != -1)
return f[n];
return f[n] = solve(n - 1) + solve(n - 2);
}
这里使用 f[] 保存已经得到的答案,使用前需要将其初始化为 -1。
每次递归时,先检查当前状态是否已经计算过。如果已经计算过,就直接返回保存的结果,否则继续递归求解。
记忆化搜索与普通递推 DP 的主要区别在于计算顺序:
记忆化搜索从目标状态开始递归,需要哪个子问题就计算哪个子问题,属于自顶向下的求解方式。
递推 DP从已知的初始状态出发,根据状态转移方程逐步计算,属于自底向上的求解方式。
两种方式都是通过保存已经求出的状态,避免重复计算。
八、状态设计
动态规划的难点一般在于状态定义和状态转移方程。
例如背包问题,使用 f[i][j] 就可以保存处理到第 $i$ 个物品、背包容量为 $j$ 时的最优价值。
对于后续计算,只需要已经保存的最优结果,没有必要重新枚举前面所有物品的选择过程。
因此,状态需要保存的是以后进行转移时仍然有用的信息。
有些题目只需要一维状态 f[i],有些则需要 f[i][j],甚至更高维的数组。
状态维度增加以后,所需要的时间和空间也可能随之增加。
所以做题时,首先应该确定状态表示什么,再分析它能够从哪些状态转移得到,而不是直接套用某一种 DP 模板。
九、时间与空间复杂度
动态规划的时间复杂度可以根据状态数量和每个状态需要进行的转移次数估算。
一般为:
例如数字三角形,共有 $O(n^2)$ 个状态,每个状态只需要检查两个前驱,时间复杂度为 $O(n^2)$。
普通 LIS 有 $n$ 个状态,每个状态最多需要枚举 $n$ 个前驱,因此时间复杂度同样为 $O(n^2)$。
对于背包问题,状态数量通常与物品数量 $n$ 和背包容量 $m$ 有关,时间复杂度为 $O(nm)$。
空间方面,可以根据状态之间的依赖关系进行优化。
例如二维 DP 中,如果第 $i$ 层只依赖第 $i-1$ 层,就可以考虑使用滚动数组,只保留计算所需要的状态。
01 背包则可以进一步压缩为一维数组。
不过空间压缩后要特别注意遍历顺序,避免当前轮计算出来的新状态影响原本的转移关系。
十、总结
动态规划并没有一套适用于所有题目的固定公式,关键还是根据题目建立状态。
一般解题过程为:
- 根据题意定义状态。
- 分析当前状态可以从哪些前驱状态转移。
- 写出状态转移方程。
- 确定初始状态和边界条件。
- 根据依赖关系确定计算顺序。
- 分析时间和空间复杂度,必要时进行优化。
常见的动态规划还有线性 DP、区间 DP、树形 DP、数位 DP、状态压缩 DP 等。
虽然题型不同,但基本思路相似,都是将原问题划分为子问题,通过已经求出的状态逐步计算最终答案。

















这一切,似未曾拥有