递推¶

换个方向想问题¶

上一课的递归是从大到小问下去：想知道 \(f(n)\)，先问 \(f(n-1)\)……问到出口再往回传。

递推是反过来的：从小到大算上来。先把最小的几项直接写死，然后用循环从第 3 项一路算到第 \(n\) 项。

	递归	递推
方向	从 \(n\) 倒着问回出口	从出口正着算到 \(n\)
工具	函数调用自己	数组 + 循环
汉诺塔思路	搬 \(n\) 个 = 搬 \(n-1\) 个 + 1 步	开数组 \(T[1..n]\) 逐项填
常见问题	重复计算、爆栈	想清楚填表顺序

两者能互相转化——本质是同一个「状态转移」思想的两种写法。竞赛里递推通常更快、更省心。

爬楼梯：递推第一课¶

问题：台阶有 \(n\) 级，每次能跨 1 级或 2 级，走到第 \(n\) 级有多少种走法？

从最后一步倒着想：最后一步要么从第 \(n-1\) 级跨 1 级上来，要么从第 \(n-2\) 级跨 2 级上来，所以

\[f(n) = f(n-1) + f(n-2)\]

——这不就是斐波那契嘛！最小的：1 级台阶 1 种，2 级台阶 2 种（跨 1+1 或直接跨 2）。

#include <iostream>
using namespace std;

long long f[95];   // 全局数组自动清零

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;
}

递推分析三步曲（第 8 章动态规划会天天用）：

定义状态：f[i] 表示走到第 i 级的走法数
找转移：f[i] = f[i-1] + f[i-2]
定边界：f[1] = 1, f[2] = 2

注意 \(n = 90\) 时 \(f(90)\) 约 \(4.7 \times 10^{18}\)，逼近 long long 上限（约 \(9.2 \times 10^{18}\)）——斐波那契型数列涨得飞快，又见溢出。

杨辉三角：二维递推¶

\[\begin{array}{cccccc} 1 & & & & & \\ 1 & 1 & & & & \\ 1 & 2 & 1 & & & \\ 1 & 3 & 3 & 1 & & \\ 1 & 4 & 6 & 4 & 1 & \end{array}\]

每个数 = 肩上两个数之和（左右两肩没有的按 1 算）：

\[a[i][j] = a[i-1][j-1] + a[i-1][j]\]

#include <iostream>
using namespace std;

long long a[25][25];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (j == 1 || j == i) a[i][j] = 1;   // 两肩边界
            else a[i][j] = a[i-1][j-1] + a[i-1][j];
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

一维递推靠一个数组，二维递推靠一张表——「当前状态由之前的状态拼出来」这个感觉，就是杨辉三角要教会你的事。它还是第 9 章组合数 \(C_i^j\) 的计算器。

递推的两点好处¶

快：每项只算一次，\(O(n)\)；朴素递归求 fib 是指数级
稳：没有递归深度限制。递归每层调用都要占一点内存，层数太深（比如几十万层）会爆栈崩溃；循环填表多少项都不怕

什么时候仍用递归？问题结构天然是「树状」的（如汉诺塔、后面的搜索）——递归写起来更自然。结构是链条的（一项接一项），优先递推。

例题 1：上台阶¶

题目描述　有 \(n\) 级台阶，每次可以跨 1 级或 2 级，求走到第 \(n\) 级的方案数。

输入格式　一个整数 \(n\)。

输出格式　一个整数。

数据范围　\(1 \le n \le 90\)。

样例输入 / 样例输出
7
21

思路分析　就是正文那三步：状态 \(f[i]\)、转移 \(f[i]=f[i-1]+f[i-2]\)、边界 \(f[1]=1,\ f[2]=2\)。本题真正的考点是数据范围逼你用 long long：\(f(90)\) 高达 \(4.6 \times 10^{18}\)，int 撑到第 47 级就溢出了。

参考代码

#include <iostream>
using namespace std;

long long f[95];

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;
}

同款题：洛谷搜「数楼梯」（进阶版数据更大，需要高精度——学有余力再战）。

例题 2：杨辉三角¶

题目描述　输出杨辉三角前 \(n\) 行。

输入格式　一个整数 \(n\)。

输出格式　\(n\) 行，第 \(i\) 行有 \(i\) 个数，空格分隔。

数据范围　\(1 \le n \le 20\)。

样例输入 / 样例输出
4
1
1 1
1 2 1
1 3 3 1

思路分析　二维递推：边界是每行首尾为 1，中间项由上一行左右两肩相加。注意数组要开全局（自动清零），下标从 1 开始能省掉越界判断。

参考代码

#include <iostream>
using namespace std;

long long a[25][25];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (j == 1 || j == i) a[i][j] = 1;
            else a[i][j] = a[i-1][j-1] + a[i-1][j];
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

洛谷搜「杨辉三角」有同款题。提示：第 \(n\) 行中间的数已经很大，别用 int。

动手试一试¶

递推求 \(1! + 2! + \cdots + n!\)（\(n \le 20\)，想想数组该怎么用、为什么最后求和也可能要 long long）
病毒繁殖：第 1 天有 1 只病毒，每天每只分裂成 2 只，第 \(n\) 天有多少只？（递推式极简单，体会「状态定义」的作用）
平面切割：\(n\) 条直线最多把平面分成几块？（提示：新增第 \(i\) 条线最多被切出 \(i\) 段，每段多分出一块；\(f(n) = f(n-1) + n\)）
思考：爬楼梯如果每次能跨 1、2 或 3 级，转移方程变成什么？

入门篇过半！ 下一章开始学真正的算法套路：第 5 章 · 基础算法。