适合阅读：初中阶段学习信息学竞赛的同学

例题来源：信息学奥赛一本通（C++版），全部 14 道递推专题题目

一、什么是递推算法？

从多米诺骨牌说起

推倒第一块骨牌，它撞倒第二块，第二块撞倒第三块……一路倒下去。你不需要亲自推每一块，只需要知道相邻两块之间的关系。

这就是递推——

递推（Recurrence）：根据前面的已知结果，按照固定的规律，一步一步推出后面的结果。

递推 vs 递归

递归 递推
方向 从大到小，不断调用自己 从小到大，逐步往上推
实现 函数调用，可能重复计算 循环 + 数组，每个值只算一次
栈 可能爆栈 安全

💡 一句话：递归是"我不知道结果，让我问问更小的问题"，递推是"我已经知道了前面的，直接算后面的"。

递推解题三步法

步骤一：找递推式    → f(n) 和 f(n-1)、f(n-2) 等前面项的关系是什么？
步骤二：确定初始值  → f(1)、f(2) 等最开头几项的值
步骤三：循环递推    → 从初值开始，一步步向后计算到目标

递推常见题型

┌─ 数列递推 ──── 菲波那契、Pell数列、上台阶……
├─ 二维路径 ──── 蚂蚁路线、过河卒
├─ 状态递推 ──── 昆虫繁殖、位数问题、踩方格
├─ 划分递推 ──── 放苹果、吃糖果
├─ 递推+DP ───── 判断整除、山区建小学
└─ 模拟递推 ──── 流感传染

二、例题精讲

第一类：数列递推 —— "第 n 项怎么从前面推出来"

菲波那契数列(2) —— "第 n 项 = 前两项之和"

题目描述

菲波那契数列：f(1)=1f(1)=1，f(2)=1f(2)=1，f(n)=f(n−1)+f(n−2)  (n>2)f(n)=f(n-1)+f(n-2)\;(n>2)。给出 aa，求 f(a) mod 1000f(a) \bmod 1000。

输入格式

  • 第一行：测试组数 nn
  • 接下来 nn 行：每行一个正整数 aa（1≤a≤1061 \le a \le 10^6）

输出格式

  • nn 行，每行 f(a) mod 1000f(a) \bmod 1000

样例输入

4
5
2
19
1

样例输出

5
1
181
1

样例解释

f(5)=5f(5)=5，f(2)=1f(2)=1，f(19)=4181 mod 1000=181f(19)=4181 \bmod 1000 = 181，f(1)=1f(1)=1。

递推策略

f[i]=(f[i−1]+f[i−2]) mod 1000f[i] = (f[i-1] + f[i-2]) \bmod 1000，从 i=3i=3 推到 i=max⁡(a)i=\max(a)。

注意 a≤106a \le 10^6，f(a)f(a) 会极大（几百位），必须每步取模。性质：(a+b) mod m=(a mod m+b mod m) mod m(a+b)\bmod m = (a\bmod m + b\bmod m)\bmod m。

C++ 代码

#include <iostream>
using namespace std;
int f[1000005];
int main() {
    int n; cin >> n;
    f[1] = f[2] = 1;
    for (int i = 3; i <= 1000000; i++)
        f[i] = (f[i-1] + f[i-2]) % 1000;
    while (n--) {
        int a; cin >> a;
        cout << f[a] << endl;
    }
    return 0;
}
要点 说明
预计算 一次算到最大值 1000000，查询直接 O(1)O(1) 输出
每步取模 利用模运算性质，防溢出

Pell 数列 —— "Pell[i] = 2×Pell[i-1] + Pell[i-2]"

题目描述

Pell 数列：a1=1a_1=1，a2=2a_2=2，an=2an−1+an−2  (n>2)a_n = 2a_{n-1} + a_{n-2}\;(n>2)。求第 kk 项模 32767。（k<106k < 10^6）

样例输入

2
1
8

样例输出

1
408

递推策略

a[i]=(2×a[i−1]+a[i−2]) mod 32767a[i] = (2 \times a[i-1] + a[i-2]) \bmod 32767

和斐波那契一模一样的套路，只是系数变了。

C++ 代码

#include <iostream>
using namespace std;
int a[1000005];
int main() {
    a[1] = 1; a[2] = 2;
    for (int i = 3; i <= 1000000; i++)
        a[i] = (2 * a[i-1] + a[i-2]) % 32767;
    int n; cin >> n;
    while (n--) {
        int k; cin >> k;
        cout << a[k] << endl;
    }
    return 0;
}
要点 说明
递推式变化 系数从 1,1 变为 2,1，但结构不变
多组查询 预计算 + 查表，O(1)O(1) 回答每个询问

上台阶 —— "一次可以走 1、2 或 3 阶"

题目描述

楼梯有 nn 阶台阶（0<n<710 < n < 71），每次可以一步上 1 阶、2 阶或 3 阶，求不同走法总数。输入多行，以 0 结束。

样例输入

1
2
3
4
0

样例输出

1
2
4
7

样例解释

  • n=1n=1：只有 1 种（走 1 阶）
  • n=2n=2：2 种（1+1 或 2）
  • n=3n=3：4 种（1+1+1、1+2、2+1、3）
  • n=4n=4：7 种

递推策略

f[1]=1f[1]=1，f[2]=2f[2]=2，f[3]=4f[3]=4，f[i]=f[i−1]+f[i−2]+f[i−3]f[i] = f[i-1] + f[i-2] + f[i-3]

为什么？ 最后一步只可能是跨 1、2 或 3 阶。跨 1 阶 → 前面 i−1i-1 阶的方案数；跨 2 阶 → 前面 i−2i-2 阶的方案数；跨 3 阶 → 前面 i−3i-3 阶的方案数。三类加起来。

C++ 代码

#include <iostream>
using namespace std;
long long f[75];
int main() {
    f[1] = 1; f[2] = 2; f[3] = 4;
    for (int i = 4; i <= 70; i++)
        f[i] = f[i-1] + f[i-2] + f[i-3];
    int n;
    while (cin >> n && n) cout << f[n] << endl;
    return 0;
}
要点 说明
三类最后一步 递推的经典套路：分类讨论最后一步的情况
long long n=70n=70 时结果很大，int 会溢出

吃糖果 —— "每天吃 1 块或 2 块，几天吃完"

题目描述

名名每天吃 1 块或 2 块巧克力。问吃完 nn 块巧克力有多少种不同的吃法。

递推策略

f[1]=1f[1]=1，f[2]=2f[2]=2，f[i]=f[i−1]+f[i−2]f[i] = f[i-1] + f[i-2]

本质就是斐波那契数列！第一天吃 1 块 → 剩 n−1n-1 块；第一天吃 2 块 → 剩 n−2n-2 块。

C++ 代码

#include <iostream>
using namespace std;
int f[25];
int main() {
    int n; cin >> n;
    f[1] = 1; f[2] = 2;
    for (int i = 3; i <= n; i++)
        f[i] = f[i-1] + f[i-2];
    cout << f[n] << endl;
    return 0;
}
要点 说明
识破 换个说法，本质就是斐波那契
初始值 1块1种，2块2种（1+1、2）

第二类：二维路径递推 —— "每一格从左边或上边来"

移动路线 —— "蚂蚁只能向右或向上"

题目描述

mm 行 nn 列方格，蚂蚁从左下角 (1,1)(1,1) 走到右上角 (m,n)(m,n)，只能向上或向右移动，每次移动一格。求不同路线数。（0<m+n≤200 < m+n \le 20）

样例输入

2 3

样例输出

3

递推策略

dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]

到达 (i,j)(i,j) 的最后一步：要么从下方 (i−1,j)(i-1,j) 上来，要么从左方 (i,j−1)(i,j-1) 过来。

C++ 代码

#include <iostream>
using namespace std;
int dp[25][25];
int main() {
    int m, n; cin >> m >> n;
    for (int i = 1; i <= m; i++) dp[i][1] = 1;
    for (int j = 1; j <= n; j++) dp[1][j] = 1;
    for (int i = 2; i <= m; i++)
        for (int j = 2; j <= n; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    cout << dp[m][n] << endl;
    return 0;
}
要点 说明
边界 第 1 行和第 1 列都只有 1 种走法
递推方向 从上到下、从左到右填表

过河卒（NOIP2002）—— "有马拦路，卒怎么走"

题目描述

棋盘 A(0,0)A(0,0) 到 B(n,m)B(n,m)（n,m≤20n,m \le 20），卒只能向下或向右。棋盘上有一匹马 CC，马所在点和所有马能一步跳到的点卒都不能走。求 AA 到 BB 的路径条数。

样例输入

8 6 0 4

样例输出

1617

递推策略

和移动路线完全相同：dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]。唯一区别：被马控制的点 dp=0dp=0 且跳过。

C++ 代码

#include <iostream>
using namespace std;
long long dp[25][25];
bool block[25][25];  // 被马控制的点
int dx[9] = {0,-2,-1,1,2,2,1,-1,-2};
int dy[9] = {0,1,2,2,1,-1,-2,-2,-1};

int main() {
    int n, m, cx, cy;
    cin >> n >> m >> cx >> cy;
    // 标记马控制点
    for (int i = 0; i < 9; i++) {
        int nx = cx + dx[i], ny = cy + dy[i];
        if (nx >= 0 && nx <= n && ny >= 0 && ny <= m)
            block[nx][ny] = true;
    }
    dp[0][0] = block[0][0] ? 0 : 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (block[i][j]) continue;
            if (i > 0) dp[i][j] += dp[i-1][j];
            if (j > 0) dp[i][j] += dp[i][j-1];
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}
要点 说明
马的控制点 用 block[][] 标记，含马自身 + 8 个跳跃点
long long 路径数可能很大
递推框架不变 只是加了障碍判断

第三类：状态递推 —— "不只一个递推式，多个数组联动"

昆虫繁殖 —— "成虫生卵，卵变成虫"

题目描述

每对成虫过 xx 个月产 yy 对卵，每对卵过 2 个月长成成虫。成虫不死，第一个月只有 1 对成虫，卵长成成虫后的第一个月不产卵（过 xx 个月才产）。问过 zz 个月后有多少对成虫。（0≤x≤200 \le x \le 20，1≤y≤201 \le y \le 20，x≤z≤50x \le z \le 50）

样例输入

1 2 8

样例输出

37

递推策略

维护两个数组：

  • egg[i]egg[i] = 第 ii 个月新增的卵对数
  • adult[i]adult[i] = 第 ii 个月的成虫对数

递推关系：

  • egg[i]=adult[i−x]×yegg[i] = adult[i-x] \times y（成虫 xx 个月前产的卵本月出生）
  • adult[i]=adult[i−1]+egg[i−2]adult[i] = adult[i-1] + egg[i-2]（成虫不死，2 个月前的卵本月长成）

C++ 代码

#include <iostream>
using namespace std;
long long egg[55], adult[55];
int main() {
    int x, y, z; cin >> x >> y >> z;
    adult[0] = 1;  // 初始 1 对成虫
    for (int i = 1; i <= z; i++) {
        if (i >= x) egg[i] = adult[i - x] * y;
        adult[i] = adult[i - 1];
        if (i >= 2) adult[i] += egg[i - 2];
    }
    cout << adult[z] << endl;
    return 0;
}
要点 说明
双数组联动 eggegg 和 adultadult 互相依赖，同时递推
延迟效应 xx 个月产卵 + 2 个月孵化，下标偏移要算对

位数问题 —— "N 位数里有多少含偶数个 3"

题目描述

在所有的 NN 位数（N≤1000N \le 1000）中，有多少个数中有偶数个数字 3？输出答案  mod 12345\bmod 12345。

样例输入

2

样例输出

73

样例解释

两位数（10~99）中，含偶数个 3 的数：除了含 1 个 3 的（13,23,43,...,93 和 30~39 除去 33 = 9+10-1=18个？实际上...）。结果 73。

递推策略

设 even[i]even[i] = ii 位数中含偶数个 3 的个数，odd[i]odd[i] = ii 位数中含奇数个 3 的个数。

  • even[i]=even[i−1]×9+odd[i−1]×1even[i] = even[i-1] \times 9 + odd[i-1] \times 1
  • odd[i]=odd[i−1]×9+even[i−1]×1odd[i] = odd[i-1] \times 9 + even[i-1] \times 1

为什么？ 在 i−1i-1 位数前加一位数字（0~9）：

  • 加非 3（9 种选择）→ 奇偶性不变
  • 加 3（1 种选择）→ 奇偶性反转

注意首位不能是 0，所以 ii 位数第一位有 8 个非 3 的选择（1~9 除 3）+ 1 个 3 选择。

C++ 代码

#include <iostream>
using namespace std;
int even[1005], odd[1005];
int main() {
    int N; cin >> N;
    even[1] = 8;   // 1位数：1,2,4,5,6,7,8,9（不含3和0）
    odd[1] = 1;    // 只有 3
    for (int i = 2; i <= N; i++) {
        even[i] = (even[i-1] * 9 + odd[i-1] * 1) % 12345;
        odd[i]  = (odd[i-1] * 9 + even[i-1] * 1) % 12345;
    }
    cout << even[N] << endl;
    return 0;
}
要点 说明
双状态 eveneven 和 oddodd — 遇到 3 互相转换
首位特殊 第一位不能是 0，初始值要单独处理
分类计数 递推中按"加几"分类讨论

踩方格 —— "只能向北、东、西走，走过的路会塌"

题目描述

n×∞n \times \infty 方格矩阵，从起点出发走 nn 步（n≤20n \le 20），每步只能向北、东、西三个方向（不能向南），走过的格子不能再走。求不同方案数。

样例输入

2

样例输出

7

递推策略

设 l[i]l[i]、r[i]r[i]、u[i]u[i] 分别表示第 ii 步以向左/向右/向上结束的方案数。

  • l[i]=l[i−1]+u[i−1]l[i] = l[i-1] + u[i-1]（上一步向左或向上，才能续向左）
  • r[i]=r[i−1]+u[i−1]r[i] = r[i-1] + u[i-1]
  • u[i]=l[i−1]+r[i−1]+u[i−1]u[i] = l[i-1] + r[i-1] + u[i-1]（上一步任何方向都可以续向上）

总数 f[i]=l[i]+r[i]+u[i]f[i] = l[i] + r[i] + u[i]。可以简化：f[i]=f[i−1]×2+f[i−2]f[i] = f[i-1] \times 2 + f[i-2]。

C++ 代码

#include <iostream>
using namespace std;
int f[25];
int main() {
    int n; cin >> n;
    f[1] = 3; f[2] = 7;
    for (int i = 3; i <= n; i++)
        f[i] = 2 * f[i-1] + f[i-2];
    cout << f[n] << endl;
    return 0;
}
要点 说明
方向分类 不能向南是关键约束，左右对称
化简 三维递推可化简为一维 f[i]=2f[i−1]+f[i−2]f[i]=2f[i-1]+f[i-2]

放苹果 —— "M 个苹果放进 N 个盘子"

题目描述

把 MM 个同样的苹果放在 NN 个同样的盘子里，允许有的盘子空着不放。问有多少种不同分法。

递推策略

f(m,n)f(m,n) = mm 个苹果放 nn 个盘子的方案数。

  • 若 n>mn > m：至少有 n−mn-m 个空盘，等价于 f(m,m)f(m,m)
  • 若 n≤mn \le m：分两类 —— 有空盘（f(m,n−1)f(m, n-1)）+ 无空盘（f(m−n,n)f(m-n, n)，每盘先放 1 个）

C++ 代码

#include <iostream>
using namespace std;
int f(int m, int n) {
    if (m == 0 || n == 1) return 1;
    if (n > m) return f(m, m);
    return f(m, n-1) + f(m-n, n);
}
int main() {
    int t, m, n; cin >> t;
    while (t--) { cin >> m >> n; cout << f(m, n) << endl; }
    return 0;
}
要点 说明
分类讨论 有空盘 / 无空盘 两个子问题
递归实现 用递归更直观，也可用递推的二维表

流感传染 —— "每天传染邻居，模拟到第 m 天"

题目描述

n×nn \times n 网格宿舍区（n≤100n \le 100），. 健康人，# 空房间，@ 病人。每天病人传染上下左右邻居（空房不传染）。求第 mm 天（m≤100m \le 100）得流感的总人数。

样例输入

5
....#
.#.@.
.#@..
#....
.....
4

样例输出

16

递推策略

逐天模拟：对于每一天，遍历网格找出当天的病人，将他们的健康邻居标记为"明天被传染"。每天结束后更新网格状态。

这是"模拟递推"——每一天的状态由前一天推出。

C++ 代码

#include <iostream>
using namespace std;
char a[105][105], b[105][105];
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};

int main() {
    int n, m; cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];
    cin >> m;

    for (int day = 1; day < m; day++) {
        // 复制当前状态
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) b[i][j] = a[i][j];
        // 传染
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (a[i][j] == '@')
                    for (int d = 0; d < 4; d++) {
                        int x = i + dx[d], y = j + dy[d];
                        if (x >= 1 && x <= n && y >= 1 && y <= n && b[x][y] == '.')
                            b[x][y] = '@';
                    }
        // 更新
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) a[i][j] = b[i][j];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (a[i][j] == '@') ans++;
    cout << ans << endl;
    return 0;
}
要点 说明
用副本 传染时需要一个"前一天的快照"b[][]，避免当天新传染的病人继续传染
方向数组 上下左右四个方向遍历

第四类：递推+DP —— "递推思想解决更复杂问题"

判断整除 —— "加减号怎么填，能被 k 整除"

题目描述

NN 个正整数序列（2<N<100002 < N < 10000），在每个数前插入 + 或 -，求是否存在一种填法使得结果能被 kk（2<k<1002 < k < 100）整除。输出 YES 或 NO。

样例输入

3 2
1 2 4

样例输出

NO

递推策略

dp[i][r]dp[i][r] = 前 ii 个数能否凑出余数 rr（ mod k\bmod k）。 由第 i−1i-1 层推第 ii 层：$dp[i][((r + a_i) \bmod k)] = dp[i][((r - a_i) \bmod k)] = true$

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
bool dp[2][105];  // 滚动数组
int main() {
    int N, K, x; cin >> N >> K;
    dp[0][0] = true;  // 空集，和为0，余数为0
    for (int i = 1; i <= N; i++) {
        cin >> x;
        int cur = i & 1, pre = cur ^ 1;
        memset(dp[cur], 0, sizeof(dp[cur]));
        x = (x % K + K) % K;
        for (int r = 0; r < K; r++) {
            if (dp[pre][r]) {
                dp[cur][(r + x) % K] = true;
                dp[cur][(r - x + K) % K] = true;
            }
        }
    }
    cout << (dp[N & 1][0] ? "YES" : "NO") << endl;
    return 0;
}
要点 说明
余数 DP 状态是余数而非具体数值，k<100k<100 很小
滚动数组 只保留前一行的状态，节省内存
负数取模 (r - x + K) % K 处理负数情况

山区建小学 —— "n 个村选 m 个建小学，距离和最小"

题目描述

mm 个村庄排在一条路上（m<500m < 500），选 nn 个建小学（n≤mn \le m）。所有学生去最近的小学。给出相邻村庄距离，求所有村庄到最近小学的距离之和的最小值。

样例输入

10 2
3 1 3 1 1 1 1 1 3

样例输出

18

递推策略

预处理 cost[i][j]cost[i][j] = 在村庄 ii 到 jj 之间只建 1 所小学的最小距离和（小学应建在中位数位置）。

dp[i][j]dp[i][j] = 前 ii 个村庄建 jj 所小学的最小距离和。 dp[i][j]=min⁡k(dp[k][j−1]+cost[k+1][i])dp[i][j] = \min_{k}(dp[k][j-1] + cost[k+1][i])

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
int d[505], s[505];          // 距离、前缀和
int cost[505][505], dp[505][505];

int main() {
    int m, n; cin >> m >> n;
    for (int i = 2; i <= m; i++) { cin >> d[i]; s[i] = s[i-1] + d[i]; }

    // 预处理 cost[i][j]: 区间[i,j]只建1所学校的最小距离和
    for (int i = 1; i <= m; i++)
        for (int j = i; j <= m; j++) {
            int mid = (i + j) / 2;  // 中位数位置
            for (int k = i; k <= j; k++)
                cost[i][j] += abs(s[k] - s[mid]);
        }

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n && j <= i; j++) {
            for (int k = j - 1; k < i; k++) {
                dp[i][j] = min(dp[i][j], dp[k][j-1] + cost[k+1][i]);
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}
要点 说明
中位数性质 区间内只建 1 所学校时，建在中位数位置总距离最小
前缀和 用 s[] 快速计算村庄间距离
二层 DP costcost 预处理 + dpdp 主递推

三、14 题总表

题号 题目 递推类型 核心递推式 复杂度
1188 菲波那契数列(2) 数列递推 f[i]=f[i−1]+f[i−2]f[i]=f[i-1]+f[i-2] O(n)O(n)
1189 Pell数列 a[i]=2a[i−1]+a[i−2]a[i]=2a[i-1]+a[i-2]
1190 上台阶 f[i]=f[i−1]+f[i−2]+f[i−3]f[i]=f[i-1]+f[i-2]+f[i-3]
1193 吃糖果 f[i]=f[i−1]+f[i−2]f[i]=f[i-1]+f[i-2]
1194 移动路线 二维路径 dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j]=dp[i-1][j]+dp[i][j-1] O(mn)O(mn)
1314 过河卒 二维路径+障碍 同上 + 马的控制点跳过 O(nm)O(nm)
1312 昆虫繁殖 双数组联动 eggegg 和 adultadult 互相依赖 O(z)O(z)
1313 位数问题 双状态 even,oddeven, odd 遇到 3 互换 O(N)O(N)
1196 踩方格 方向分类递推 f[i]=2f[i−1]+f[i−2]f[i]=2f[i-1]+f[i-2] O(n)O(n)
1192 放苹果 划分递推 f(m,n)=f(m,n−1)+f(m−n,n)f(m,n)=f(m,n-1)+f(m-n,n) O(mn)O(mn)
1191 流感传染 模拟递推 逐天传染邻居 O(m⋅n2)O(m \cdot n^2)
1195 判断整除 余数DP dp[i][(r±ai) mod k]=truedp[i][(r \pm a_i)\bmod k]=true O(Nk)O(Nk)
1197 山区建小学 区间DP dp[i][j]=min⁡(dp[k][j−1]+cost[k+1][i])dp[i][j]=\min(dp[k][j-1]+cost[k+1][i]) O(m2n)O(m^2n)

递推题型分类速查

┌─ 数列递推 ──── 菲波那契、Pell数列、上台阶、吃糖果
│               （一项或多项前面项推出当前项）
│
├─ 二维路径 ──── 移动路线、过河卒
│               （dp[i][j] = dp[i-1][j] + dp[i][j-1]）
│
├─ 状态递推 ──── 昆虫繁殖、位数问题、踩方格
│               （多个递推数组联动 / 特殊方向约束）
│
├─ 划分递推 ──── 放苹果
│               （分类讨论空/非空，递推分解子问题）
│
├─ 模拟递推 ──── 流感传染
│               （逐天/逐轮模拟状态变化）
│
└─ 递推+DP ──── 判断整除、山区建小学
                （递推填表法解决更复杂的DP问题）

递推解题三步法

步骤一：找递推式    → f(n) 和前面几项的关系（仔细分析最后一步 / 分类讨论）
步骤二：确定初始值  → f(1) / f(2) 等边界，递推的起点
步骤三：循环递推    → 从初值开始，for 循环逐项推到目标（多组询问可先预处理）

递推常见初始化套路

场景 初始化方式
数列递推（前两项给定） f[1]=a, f[2]=b
二维路径（边界为 1） dp[i][1]=1, dp[1][j]=1
有障碍的路径 边界有障碍则之后全为 0
双状态递推 分别给初值
模拟递推 直接按第一天状态输入
求最小值（DP） memset(dp, 0x3f)，dp[0]=0

💡 记住：递推的本质就是填表。找到前后项的关系，定好初始值，剩下的就是写循环。相较于 DP，递推更简单直接 —— 它是你学习动态规划的最好跳板。14 道题吃透，递推就彻底掌握了。加油！

  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. Edited & Maintained by sstzer
  3. Worker 0, 110ms
  4. Powered by Hydro v4.19.1 Community