动态规划（DP）的引入

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

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

从递归到动态规划

先看一个很简单的问题：走上$n$级台阶，每次可以走$1$级或$2$级，一共有多少种走法？

定义$f_i$表示走到第$i$级台阶的方案数。最后一步只可能从$i-1$走一级，或者从$i-2$走两级，因此：

$$
f_i=f_{i-1}+f_{i-2}
$$

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

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

解决方法有两种：

1. 记忆化搜索：仍然从$f_n$向下递归，但每个状态第一次算完以后保存起来；
2. 递推：从$f_0,f_1$开始，按照$f_2,f_3,\ldots,f_n$的顺序向后计算。

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

写出一个DP

状态

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

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

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

转移

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

$$
f_i=\max(f_j+w_{j,i})
$$

$$
f_i=\min(f_j+w_{j,i})
$$

$$
f_i=\sum f_j
$$

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

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

初始化

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

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

计算顺序

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

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

常见模型与例题

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

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

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

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

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

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

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

考虑以$a_i$结尾的子段，只有两种选择：

1. 把$a_i$接在以$a_{i-1}$结尾的最优子段后面，得到$f_{i-1}+a_i$；
2. 不保留前面的子段，从$a_i$重新开始。

于是：

$$
f_i=\max(f_{i-1}+a_i,a_i)
$$

边界为$f_1=a_1$。由于$f_i$只表示“必须以$i$结尾”的答案，整个序列的最大子段可能在任意位置结束，所以最终答案是：

$$
ans=\max_{1\le i\le n}f_i
$$

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

点击展开完整代码

/* 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(1)$。

例题二：AtCoder DP A Frog 1

题目链接：AtCoder DP A Frog 1

有$n$个高度分别为$h_1,h_2,\ldots,h_n$的石头。青蛙最初位于第$1$块石头，每次可以跳到下一块或下两块石头，从$i$跳到$j$的代价为$\lvert h_i-h_j\rvert$，求到达第$n$块石头的最小总代价。

定义$f_i$表示到达第$i$块石头的最小总代价。

到达$i$的最后一步只可能来自$i-1$或$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)
$$

青蛙一开始就在第$1$块石头，所以$f_1=0$。第$2$块石头只能从第$1$块到达：

$$
f_2=\lvert h_2-h_1\rvert
$$

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

点击展开完整代码

/* 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(1)$空间，不过入门阶段保留数组更容易观察每个状态的含义。

例题三：洛谷 P1002 过河卒

题目链接：洛谷 P1002 过河卒

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

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

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

$$
f_{i,j}=f_{i-1,j}+f_{i,j-1}
$$

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

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

点击展开完整代码

/* 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)$。

状态压缩与常见错误

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

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

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

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

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

常见问题与复杂度分析

常见问题

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

复杂度分析

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

系列文章

1. 动态规划（DP）的引入
2. 线性dp