📘简单递推

📖概念讲解

递推是动态规划的前置技能，本质就是找规律、推公式：从已知的初始条件出发，一步步推出后面的结果。

和递归不同，递推是从小往大算（正推），不用函数调用自己，不容易爆栈。核心步骤：

• ① 定义 f[i] 的含义——"第 i 个状态的值"
• ② 找递推关系式——f[i] 和前面哪些 f[j] 有关
• ③ 确定初始条件（base case）
• ④ 按顺序填表

💻代码示例

经典例题：爬楼梯。每次可以走 1 阶或 2 阶，问到第 n 阶有多少种走法。

💡 这个递推式和斐波那契一模一样：f[n] = f[n-1] + f[n-2]。递推比递归快得多，因为没有重复计算。

🧩互动小测

🏋️动手练一练

#include <iostream>
using namespace std;

int main() {
    int n;  cin >> n;
    long long f[50] = {0};    // 用 long long 防溢出
    f[1] = 1;                 // 只能放 1×1
    f[2] = 2;                 // 两个1×1 或 一个1×2
    for (int i = 3; i <= n; i++)
        f[i] = f[i-1] + f[i-2];  // 最后放1×1 + 最后放1×2
    cout << f[n] << endl;
    return 0;
}
// 输入 4 → 输出 5

📝易错点提醒

• 递推顺序不能乱：算 f[i] 之前，它依赖的 f[i-1]、f[i-2] 必须已经算好。
• 初始条件别漏：f[1] 和 f[2] 要手动赋值，循环从 i=3 开始。
• 数组大小：n 最大 40，f[] 开到 50 就够；但如果 n 到 10^5 以上，考虑只保留前两个值滚动数组。
• int vs long long：递推值增长很快，n>35 左右就可能爆 int，考试中建议直接用 long long。