动态规划并不是一段固定的模板,而是一种组织计算的方式:把原问题拆成若干个状态,先求出较小状态的答案,再利用它们得到更大的状态。

它解决的也不只是“求最大值”。最小代价、方案数量、能否到达,都可以使用动态规划。真正需要想清楚的只有几件事:状态表示什么、如何转移、从哪里开始,以及按照什么顺序计算。

从递归到动态规划

先看一个很简单的问题:走上nn级台阶,每次可以走11级或22级,一共有多少种走法?

定义fif_i表示走到第ii级台阶的方案数。最后一步只可能从i−1i-1走一级,或者从i−2i-2走两级,因此:

fi=fi−1+fi−2f_i=f_{i-1}+f_{i-2}

边界为f0=1,f1=1f_0=1,f_1=1。f0=1f_0=1表示什么都不走也算一种完整方案,这样f2=f1+f0=2f_2=f_1+f_0=2可以自然成立。

如果直接递归计算fnf_n,同一个fif_i会被反复求很多次。例如fnf_n与fn−1f_{n-1}都会继续计算fn−2f_{n-2},规模稍大就会变得很慢。

解决方法有两种:

  1. 记忆化搜索:仍然从fnf_n向下递归,但每个状态第一次算完以后保存起来;
  2. 递推:从f0,f1f_0,f_1开始,按照f2,f3,…,fnf_2,f_3,\ldots,f_n的顺序向后计算。

两种写法本质上做的是同一件事:让每个状态只计算一次,并保存结果供后面使用。前者是自顶向下,后者是自底向上;通常所说的DP更接近第二种写法。

写出一个DP

状态

状态要说明两个问题:下标代表什么,数组中保存什么。

例如“fif_i表示前ii个数的最大值”仍然不够清楚;“fif_i表示必须以第ii个数结尾的最大子段和”才是一个可以直接用于转移的定义。

状态记录的信息不能太少。若两个局面虽然位置相同,但剩余次数、上一步选择或已使用物品不同,并且这些信息会影响后续答案,就必须把它们加入状态。反过来,与未来无关的历史过程不需要保留,否则状态数量会无谓增大。

转移

状态转移描述当前状态如何由更小的状态得到。常见形式包括:

fi=max⁡(fj+wj,i)f_i=\max(f_j+w_{j,i})

fi=min⁡(fj+wj,i)f_i=\min(f_j+w_{j,i})

fi=∑fjf_i=\sum f_j

三种形式分别对应最大值、最小值和方案数。写转移时不能只看公式,还要说清楚它代表哪一种选择,以及这些选择是否覆盖全部情况、是否发生重复。

转移可以理解成两种方向:枚举当前状态的前驱,把贡献收集到当前状态;或者枚举当前状态的后继,把贡献发送出去。入门题通常使用前一种方式更容易说明。

初始化

初始化是整个递推的起点。方案数问题经常把起点设为11;最小值问题通常把未到达状态设为无穷大;最大值问题则可能需要设为负无穷,不能习惯性地全部初始化成00。

例如最大子段和允许所有元素均为负数。如果把答案初始化成00,就会错误地得到“一个数也不选”,但题目要求子段非空。

计算顺序

计算当前状态以前,它依赖的状态必须已经得到答案。如果fif_i依赖fi−1f_{i-1},就应从小到大枚举ii;如果二维状态fi,jf_{i,j}依赖上方和左侧,就要保证上方所在的行与当前行的左侧已经处理完成。

所谓无后效性,指的是当前状态一旦确定,后面的转移不再需要知道它是通过哪条具体路径得到的。并不是“过去完全不重要”,而是所有会影响未来的信息都已经包含在状态中。

常见模型与例题

下面三道题分别求最大值、最小值和方案数。题目不多,但足够把状态、转移、初始化和计算顺序串起来。

题目 状态类型 核心区别
洛谷 P1115 最大子段和 一维最大值DP 答案不一定是fnf_n
AtCoder DP A Frog 1 一维最小值DP 当前状态有两个前驱
洛谷 P1002 过河卒 二维计数DP 障碍点不能参与转移

例题一:洛谷 P1115 最大子段和

题目链接:洛谷 P1115 最大子段和

给出一个长度为nn的序列,选择其中连续且非空的一段,使这段的和最大。

如果直接定义fif_i为前ii个数中的最大子段和,就很难判断aia_i能否接在原来的最优子段后面。原来的最优子段可能早已结束,并不与aia_i相邻。

因此定义fif_i表示必须以第ii个数结尾的最大子段和。

考虑以aia_i结尾的子段,只有两种选择:

  1. 把aia_i接在以ai−1a_{i-1}结尾的最优子段后面,得到fi−1+aif_{i-1}+a_i;
  2. 不保留前面的子段,从aia_i重新开始。

于是:

fi=max⁡(fi−1+ai,ai)f_i=\max(f_{i-1}+a_i,a_i)

边界为f1=a1f_1=a_1。由于fif_i只表示“必须以ii结尾”的答案,整个序列的最大子段可能在任意位置结束,所以最终答案是:

ans=max⁡1≤i≤nfians=\max_{1\le i\le n}f_i

转移只依赖前一个状态,可以用一个变量保存fi−1f_{i-1}。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
i64 x;
cin >> x;
i64 f = x, ans = x;
for (int i = 2; i <= n; i++) {
cin >> x;
f = max(f + x, x);
ans = max(ans, f);
}
cout << ans << '\n';
return 0;
}

每个元素只处理一次,时间复杂度为O(n)O(n),空间复杂度为O(1)O(1)。

例题二:AtCoder DP A Frog 1

题目链接:AtCoder DP A Frog 1

有nn个高度分别为h1,h2,…,hnh_1,h_2,\ldots,h_n的石头。青蛙最初位于第11块石头,每次可以跳到下一块或下两块石头,从ii跳到jj的代价为∣hi−hj∣\lvert h_i-h_j\rvert,求到达第nn块石头的最小总代价。

定义fif_i表示到达第ii块石头的最小总代价。

到达ii的最后一步只可能来自i−1i-1或i−2i-2,因此:

fi=min⁡(fi−1+∣hi−hi−1∣,fi−2+∣hi−hi−2∣)f_i=\min\left(f_{i-1}+\lvert h_i-h_{i-1}\rvert, f_{i-2}+\lvert h_i-h_{i-2}\rvert\right)

青蛙一开始就在第11块石头,所以f1=0f_1=0。第22块石头只能从第11块到达:

f2=∣h2−h1∣f_2=\lvert h_2-h_1\rvert

由于fif_i只依赖编号更小的状态,按照i=3,4,…,ni=3,4,\ldots,n的顺序计算即可。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<i64> h(n + 1), f(n + 1);
for (int i = 1; i <= n; i++) cin >> h[i];
f[2] = abs(h[2] - h[1]);
for (int i = 3; i <= n; i++)
f[i] = min(f[i - 1] + abs(h[i] - h[i - 1]), f[i - 2] + abs(h[i] - h[i - 2]));
cout << f[n] << '\n';
return 0;
}

时间复杂度为O(n)O(n),当前写法的空间复杂度为O(n)O(n)。因为转移只依赖前两个状态,也可以继续压缩到O(1)O(1)空间,不过入门阶段保留数组更容易观察每个状态的含义。

例题三:洛谷 P1002 过河卒

题目链接:洛谷 P1002 过河卒

卒从(0,0)(0,0)出发,只能向右或向下移动,目标是(n,m)(n,m)。棋盘上还有一匹马,马所在的位置与它一步能够跳到的位置均不能经过,求卒到达终点的方案数。

“马拦过河卒”问题的棋盘、起点终点与马的控制点

定义fi,jf_{i,j}表示从(0,0)(0,0)走到(i,j)(i,j)的方案数。

如果(i,j)(i,j)不是马的控制点,那么最后一步只能从上方(i−1,j)(i-1,j)或左侧(i,j−1)(i,j-1)走来:

fi,j=fi−1,j+fi,j−1f_{i,j}=f_{i-1,j}+f_{i,j-1}

起点本身表示一种已经存在的方案,因此初始化f0,0=1f_{0,0}=1。第00行和第00列不需要单独写转移,只要在访问上方或左侧以前判断下标是否合法即可。

马的控制范围包括马所在的位置,一共最多99个点。先把这些位置标记为blocked,遇到控制点直接跳过,不让它接收任何方案数。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

i64 f[25][25];
bool blocked[25][25];
int dx[9] = {0, 1, 1, 2, 2, -1, -1, -2, -2};
int dy[9] = {0, 2, -2, 1, -1, 2, -2, 1, -1};

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, x, y;
cin >> n >> m >> x >> y;
for (int i = 0; i < 9; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx <= n && ny >= 0 && ny <= m) blocked[nx][ny] = true;
}
f[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (blocked[i][j] || (i == 0 && j == 0)) continue;
if (i > 0) f[i][j] += f[i - 1][j];
if (j > 0) f[i][j] += f[i][j - 1];
}
}
cout << f[n][m] << '\n';
return 0;
}

棋盘上的每个位置只处理一次,时间复杂度为O(nm)O(nm),空间复杂度为O(nm)O(nm)。

状态压缩与常见错误

状态压缩并不是另一种DP,只是发现旧状态以后不会再被使用,于是复用它们占据的空间。

最大子段和的fif_i只依赖fi−1f_{i-1},所以一个变量就够了;Frog 1只依赖前两个状态,也可以用两个变量滚动;过河卒只依赖上一行与当前行左侧,可以压缩成一维数组。

不过在刚写出转移时,不必急着压缩。数组版本更接近状态定义,也更方便检查。先保证转移正确,再根据依赖范围处理空间通常更稳妥。

入门阶段常见的问题主要有下面几种:

  • 状态含义不完整:只记录当前位置,却遗漏会影响后续的剩余次数、上一步选择等信息;
  • 初始化与题意不符:最大值问题全部设成00,导致凭空出现“不选择任何元素”的方案;
  • 答案位置判断错误:有些题的答案是fnf_n,最大子段和却需要统计所有fif_i;
  • 计算顺序错误:当前状态依赖的前驱还没有计算,或者原本需要的旧值已经被覆盖;
  • 重复或遗漏方案:计数DP必须确保不同转移对应的方案互不重复,并且覆盖全部情况;
  • 整数类型过小:方案数往往增长很快,题目没有取模时尤其要检查是否需要i64。

常见问题与复杂度分析

常见问题

  • 看到递推式就是DP吗? 不一定。DP更关心状态是否被重复使用、状态之间是否存在明确依赖,以及能否按照依赖顺序只计算一次。
  • 状态应该定义成“前ii个”还是“以ii结尾”? 取决于转移需要什么信息。最大子段和必须知道子段能否与aia_i相连,因此需要“以ii结尾”;Frog 1只关心到达ii的最小代价,定义成“到达ii”即可。
  • 为什么有时答案是fnf_n,有时还要额外维护ansans? 如果题目目标就是到达最后一个状态,答案通常是fnf_n;如果最优方案可以在任意位置结束,就需要在所有合法状态中取最优值。
  • 记忆化搜索和递推应该选哪一个? 转移顺序清楚、状态规则整齐时优先递推;状态只会访问其中一部分,或者递归关系更自然时,可以使用记忆化搜索。
  • 什么时候可以状态压缩? 当后续转移只依赖有限的前几层,并且被覆盖的状态不会再次使用时才可以压缩。

复杂度分析

题目 时间复杂度 空间复杂度
最大子段和 O(n)O(n) O(1)O(1)
AtCoder Frog 1 O(n)O(n) O(n)O(n)
过河卒 O(nm)O(nm) O(nm)O(nm)

系列文章

  1. 动态规划(DP)的引入
  2. 线性dp