递推

✨ 什么是递推？¶

递推（Iteration / Dynamic Programming - Bottom-Up） 是一种通过从小到大逐步推导来解决问题的方法，与递归 自顶向下 相对，递推是 自底向上 的过程。

递推就是我们熟悉的 写一个循环来推公式，适合问题中每个状态都依赖于较小状态的情况。

本质：利用一个数组或变量，按顺序从已知初始值开始，逐步构造出目标结果。

🆚 与递归的对比¶

特点	递归（Recursion）	递推（Iteration）
执行方向	自顶向下	自底向上
调用结构	函数调用自身	使用循环
空间消耗	有调用栈开销	一般较少
复杂度	有时重复计算	每个子问题只算一次
易理解性	更贴合数学定义	更接近计算实现

📦 递推解题的基本步骤¶

明确状态表示
确定初始值（边界）
找出状态转移方程
使用 for 循环按顺序计算

🧠 示例：斐波那契数列（递推实现）¶

我们要求第 n 个斐波那契数：

数列定义：

\[ F(1) = 1,\quad F(2) = 1,\quad F(n) = F(n-1) + F(n-2)\quad (n \ge 3) \]

🚀 C++ 实现（数组方式）¶

const int N = 1e5 + 5, mod = 998244353;
int fib[N];

fib[1] = fib[2] = 1;
for (int i = 3; i <= n; i++) 
{
    fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
}

🧮 空间优化（滚动数组）¶

int a = 1, b = 1, c;
for (int i = 3; i <= n; i++) 
{
    c = (a + b) % mod;
    a = b;
    b = c;
}

时间复杂度：$O(n)$ 空间复杂度：$O(1)$（优化后）

🧩 二维递推例子¶

例题1：杨辉三角¶

杨辉三角是组合数 $C(n, k)$ 的排列形式。

状态转移：

\[ C(n, k) = C(n-1, k-1) + C(n-1, k) \]

边界条件：

\[ C(n, 0) = C(n, n) = 1 \]

C++ 实现：¶

const int N = 1005, mod = 1e9 + 7;
int C[N][N];

for (int i = 0; i <= n; i++) 
{
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++)
    {
        C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) mod;
    }
}

例题2：棋盘路径数¶

给定一个 $n \times m$ 的棋盘，从 $(1, 1)$ 出发，每次只能向右或向下，求到达 $(n, m)$ 的路径数。

状态表示：

$dp[i][j]$ 表示走到格子 $(i, j)$ 的方案数

递推关系：

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

走到格子 $(i,j)$ 的方案等于走到格子 $(i-1,j)$ 的方案数加上走到格子 $(i,j-1)$ 的方案数。

边界条件：

第一行和第一列只有一种走法（一直向右或一直向下）

C++ 实现：¶

const int N = 1005, mod = 998244353;
int dp[N][N];

dp[1][1] = 1;
for (int i = 1; i <= n; i++) 
{
    for (int j = 1; j <= m; j++) 
    {
        if (i > 1) dp[i][j] += dp[i - 1][j];
        if (j > 1) dp[i][j] += dp[i][j - 1];
        dp[i][j] %= mod;
    }
}
cout << dp[n][m];

📌 说明：¶

时间复杂度：$O(n \cdot m)$
空间可以进一步滚动优化为一维数组

✅ 适合用递推的场景¶

子问题之间无重叠计算（从前推后）
问题可以明确列出状态转移公式
不需要回溯路径或多分支选择

常见如：

数列求值
动态规划问题（线性 DP、背包、状态转移）
计数类问题

💬 小结¶

递推写法更贴近程序员的循环思维
若状态较多或可以线性推进，优先考虑递推
若问题是 分治式 的、需要 尝试所有可能 的，递归 + 回溯更适合

📌 建议同学在写完递归后，尝试转化为递推，训练 状态表达能力 与 边界思维，为动态规划打好基础！