动态规划并不是一段固定的模板,而是一种组织计算的方式:把原问题拆成若干个状态,先求出较小状态的答案,再利用它们得到更大的状态。
它解决的也不只是“求最大值”。最小代价、方案数量、能否到达,都可以使用动态规划。真正需要想清楚的只有几件事:状态表示什么、如何转移、从哪里开始,以及按照什么顺序计算。
从递归到动态规划
先看一个很简单的问题:走上n n n 级台阶,每次可以走1 1 1 级或2 2 2 级,一共有多少种走法?
定义f i f_i f i 表示走到第i i i 级台阶的方案数。最后一步只可能从i − 1 i-1 i − 1 走一级,或者从i − 2 i-2 i − 2 走两级,因此:
f i = f i − 1 + f i − 2 f_i=f_{i-1}+f_{i-2}
f i = f i − 1 + f i − 2
边界为f 0 = 1 , f 1 = 1 f_0=1,f_1=1 f 0 = 1 , f 1 = 1 。f 0 = 1 f_0=1 f 0 = 1 表示什么都不走也算一种完整方案,这样f 2 = f 1 + f 0 = 2 f_2=f_1+f_0=2 f 2 = f 1 + f 0 = 2 可以自然成立。
如果直接递归计算f n f_n f n ,同一个f i f_i f i 会被反复求很多次。例如f n f_n f n 与f n − 1 f_{n-1} f n − 1 都会继续计算f n − 2 f_{n-2} f n − 2 ,规模稍大就会变得很慢。
解决方法有两种:
记忆化搜索 :仍然从f n f_n f n 向下递归,但每个状态第一次算完以后保存起来;
递推 :从f 0 , f 1 f_0,f_1 f 0 , f 1 开始,按照f 2 , f 3 , … , f n f_2,f_3,\ldots,f_n f 2 , f 3 , … , f n 的顺序向后计算。
两种写法本质上做的是同一件事:让每个状态只计算一次,并保存结果供后面使用 。前者是自顶向下,后者是自底向上;通常所说的DP更接近第二种写法。
写出一个DP
状态
状态要说明两个问题:下标代表什么,数组中保存什么 。
例如“f i f_i f i 表示前i i i 个数的最大值”仍然不够清楚;“f i f_i f i 表示必须以第i i i 个数结尾的最大子段和”才是一个可以直接用于转移的定义。
状态记录的信息不能太少。若两个局面虽然位置相同,但剩余次数、上一步选择或已使用物品不同,并且这些信息会影响后续答案,就必须把它们加入状态。反过来,与未来无关的历史过程不需要保留,否则状态数量会无谓增大。
转移
状态转移描述当前状态如何由更小的状态得到。常见形式包括:
f i = max ( f j + w j , i ) f_i=\max(f_j+w_{j,i})
f i = max ( f j + w j , i )
f i = min ( f j + w j , i ) f_i=\min(f_j+w_{j,i})
f i = min ( f j + w j , i )
f i = ∑ f j f_i=\sum f_j
f i = ∑ f j
三种形式分别对应最大值、最小值和方案数。写转移时不能只看公式,还要说清楚它代表哪一种选择,以及这些选择是否覆盖全部情况、是否发生重复。
转移可以理解成两种方向:枚举当前状态的前驱,把贡献收集到当前状态;或者枚举当前状态的后继,把贡献发送出去。入门题通常使用前一种方式更容易说明。
初始化
初始化是整个递推的起点。方案数问题经常把起点设为1 1 1 ;最小值问题通常把未到达状态设为无穷大;最大值问题则可能需要设为负无穷,不能习惯性地全部初始化成0 0 0 。
例如最大子段和允许所有元素均为负数。如果把答案初始化成0 0 0 ,就会错误地得到“一个数也不选”,但题目要求子段非空。
计算顺序
计算当前状态以前,它依赖的状态必须已经得到答案。如果f i f_i f i 依赖f i − 1 f_{i-1} f i − 1 ,就应从小到大枚举i i i ;如果二维状态f i , j f_{i,j} f i , j 依赖上方和左侧,就要保证上方所在的行与当前行的左侧已经处理完成。
所谓无后效性,指的是当前状态一旦确定,后面的转移不再需要知道它是通过哪条具体路径得到的。并不是“过去完全不重要”,而是所有会影响未来的信息都已经包含在状态中。
常见模型与例题
下面三道题分别求最大值、最小值和方案数。题目不多,但足够把状态、转移、初始化和计算顺序串起来。
题目
状态类型
核心区别
洛谷 P1115 最大子段和
一维最大值DP
答案不一定是f n f_n f n
AtCoder DP A Frog 1
一维最小值DP
当前状态有两个前驱
洛谷 P1002 过河卒
二维计数DP
障碍点不能参与转移
例题一:洛谷 P1115 最大子段和
题目链接:洛谷 P1115 最大子段和
给出一个长度为n n n 的序列,选择其中连续且非空的一段,使这段的和最大。
如果直接定义f i f_i f i 为前i i i 个数中的最大子段和,就很难判断a i a_i a i 能否接在原来的最优子段后面。原来的最优子段可能早已结束,并不与a i a_i a i 相邻。
因此定义f i f_i f i 表示必须以第i i i 个数结尾的最大子段和。
考虑以a i a_i a i 结尾的子段,只有两种选择:
把a i a_i a i 接在以a i − 1 a_{i-1} a i − 1 结尾的最优子段后面,得到f i − 1 + a i f_{i-1}+a_i f i − 1 + a i ;
不保留前面的子段,从a i a_i a i 重新开始。
于是:
f i = max ( f i − 1 + a i , a i ) f_i=\max(f_{i-1}+a_i,a_i)
f i = max ( f i − 1 + a i , a i )
边界为f 1 = a 1 f_1=a_1 f 1 = a 1 。由于f i f_i f i 只表示“必须以i i i 结尾”的答案,整个序列的最大子段可能在任意位置结束,所以最终答案是:
a n s = max 1 ≤ i ≤ n f i ans=\max_{1\le i\le n}f_i
an s = 1 ≤ i ≤ n max f i
转移只依赖前一个状态,可以用一个变量保存f i − 1 f_{i-1} f i − 1 。
点击展开完整代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #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 ( n ) ,空间复杂度为O ( 1 ) O(1) O ( 1 ) 。
例题二:AtCoder DP A Frog 1
题目链接:AtCoder DP A Frog 1
有n n n 个高度分别为h 1 , h 2 , … , h n h_1,h_2,\ldots,h_n h 1 , h 2 , … , h n 的石头。青蛙最初位于第1 1 1 块石头,每次可以跳到下一块或下两块石头,从i i i 跳到j j j 的代价为∣ h i − h j ∣ \lvert h_i-h_j\rvert ∣ h i − h j ∣ ,求到达第n n n 块石头的最小总代价。
定义f i f_i f i 表示到达第i i i 块石头的最小总代价。
到达i i i 的最后一步只可能来自i − 1 i-1 i − 1 或i − 2 i-2 i − 2 ,因此:
f i = min ( f i − 1 + ∣ h i − h i − 1 ∣ , f i − 2 + ∣ h i − h i − 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)
f i = min ( f i − 1 + ∣ h i − h i − 1 ∣ , f i − 2 + ∣ h i − h i − 2 ∣ )
青蛙一开始就在第1 1 1 块石头,所以f 1 = 0 f_1=0 f 1 = 0 。第2 2 2 块石头只能从第1 1 1 块到达:
f 2 = ∣ h 2 − h 1 ∣ f_2=\lvert h_2-h_1\rvert
f 2 = ∣ h 2 − h 1 ∣
由于f i f_i f i 只依赖编号更小的状态,按照i = 3 , 4 , … , n i=3,4,\ldots,n i = 3 , 4 , … , n 的顺序计算即可。
点击展开完整代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #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(n) O ( n ) 。因为转移只依赖前两个状态,也可以继续压缩到O ( 1 ) O(1) O ( 1 ) 空间,不过入门阶段保留数组更容易观察每个状态的含义。
例题三:洛谷 P1002 过河卒
题目链接:洛谷 P1002 过河卒
卒从( 0 , 0 ) (0,0) ( 0 , 0 ) 出发,只能向右或向下移动,目标是( n , m ) (n,m) ( n , m ) 。棋盘上还有一匹马,马所在的位置与它一步能够跳到的位置均不能经过,求卒到达终点的方案数。
定义f i , j f_{i,j} f i , j 表示从( 0 , 0 ) (0,0) ( 0 , 0 ) 走到( i , j ) (i,j) ( i , j ) 的方案数。
如果( i , j ) (i,j) ( i , j ) 不是马的控制点,那么最后一步只能从上方( i − 1 , j ) (i-1,j) ( i − 1 , j ) 或左侧( i , j − 1 ) (i,j-1) ( i , j − 1 ) 走来:
f i , j = f i − 1 , j + f i , j − 1 f_{i,j}=f_{i-1,j}+f_{i,j-1}
f i , j = f i − 1 , j + f i , j − 1
起点本身表示一种已经存在的方案,因此初始化f 0 , 0 = 1 f_{0,0}=1 f 0 , 0 = 1 。第0 0 0 行和第0 0 0 列不需要单独写转移,只要在访问上方或左侧以前判断下标是否合法即可。
马的控制范围包括马所在的位置,一共最多9 9 9 个点。先把这些位置标记为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 #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 ( n m ) O(nm) O ( nm ) ,空间复杂度为O ( n m ) O(nm) O ( nm ) 。
状态压缩与常见错误
状态压缩并不是另一种DP,只是发现旧状态以后不会再被使用,于是复用它们占据的空间。
最大子段和的f i f_i f i 只依赖f i − 1 f_{i-1} f i − 1 ,所以一个变量就够了;Frog 1只依赖前两个状态,也可以用两个变量滚动;过河卒只依赖上一行与当前行左侧,可以压缩成一维数组。
不过在刚写出转移时,不必急着压缩。数组版本更接近状态定义,也更方便检查。先保证转移正确,再根据依赖范围处理空间通常更稳妥。
入门阶段常见的问题主要有下面几种:
状态含义不完整 :只记录当前位置,却遗漏会影响后续的剩余次数、上一步选择等信息;
初始化与题意不符 :最大值问题全部设成0 0 0 ,导致凭空出现“不选择任何元素”的方案;
答案位置判断错误 :有些题的答案是f n f_n f n ,最大子段和却需要统计所有f i f_i f i ;
计算顺序错误 :当前状态依赖的前驱还没有计算,或者原本需要的旧值已经被覆盖;
重复或遗漏方案 :计数DP必须确保不同转移对应的方案互不重复,并且覆盖全部情况;
整数类型过小 :方案数往往增长很快,题目没有取模时尤其要检查是否需要i64 。
常见问题与复杂度分析
常见问题
看到递推式就是DP吗? 不一定。DP更关心状态是否被重复使用、状态之间是否存在明确依赖,以及能否按照依赖顺序只计算一次。
状态应该定义成“前i i i 个”还是“以i i i 结尾”? 取决于转移需要什么信息。最大子段和必须知道子段能否与a i a_i a i 相连,因此需要“以i i i 结尾”;Frog 1只关心到达i i i 的最小代价,定义成“到达i i i ”即可。
为什么有时答案是f n f_n f n ,有时还要额外维护a n s ans an s ? 如果题目目标就是到达最后一个状态,答案通常是f n f_n f n ;如果最优方案可以在任意位置结束,就需要在所有合法状态中取最优值。
记忆化搜索和递推应该选哪一个? 转移顺序清楚、状态规则整齐时优先递推;状态只会访问其中一部分,或者递归关系更自然时,可以使用记忆化搜索。
什么时候可以状态压缩? 当后续转移只依赖有限的前几层,并且被覆盖的状态不会再次使用时才可以压缩。
复杂度分析
题目
时间复杂度
空间复杂度
最大子段和
O ( n ) O(n) O ( n )
O ( 1 ) O(1) O ( 1 )
AtCoder Frog 1
O ( n ) O(n) O ( n )
O ( n ) O(n) O ( n )
过河卒
O ( n m ) O(nm) O ( nm )
O ( n m ) O(nm) O ( nm )
系列文章
动态规划(DP)的引入 线性dp