递推算法模板

#include <bits/stdc++.h>
using namespace std;

int main() {
    // ====== 1. 斐波那契数列 ======
    // f(1)=1, f(2)=1, f(n)=f(n-1)+f(n-2)
    const int N = 50;
    long long fib[N + 1];
    fib[1] = fib[2] = 1;
    for (int i = 3; i <= N; i++)
        fib[i] = fib[i-1] + fib[i-2];
    cout << fib[10] << endl;  // 55

    // ====== 2. 爬楼梯 ======
    // 每次走1或2步，到第n阶有多少种走法
    int n = 10;
    long long dp[n + 1];
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];

    // ====== 3. 上台阶（1/2/3步）======
    dp[1] = 1; dp[2] = 2; dp[3] = 4;
    for (int i = 4; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

    // ====== 4. 数塔问题 ======
    int m = 5;
    int tower[10][10] = {
        {5}, {8,3}, {12,7,16}, {4,10,11,6}, {9,5,3,8,7}
    };
    // 从底部往上递推
    for (int i = m-2; i >= 0; i--)
        for (int j = 0; j <= i; j++)
            tower[i][j] += max(tower[i+1][j], tower[i+1][j+1]);
    cout << tower[0][0] << endl;

    return 0;
}

📖 要点说明

• 递推三步：定义状态→找转移方程→确定初始值
• 递推和递归等价，但递推无栈溢出风险
• 注意数据范围：fib 增长很快，需用 long long

⚠️ 常见错误

• 初始值设错导致后续全错
• 结果溢出：fib(50) 远超 int 范围
• 数塔递推方向搞反：应从底向上