假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

一、思想

动态规划的思想，对于第 n 个台阶，考虑从 n-1 和 n-2 台阶过来的情况

二、源码

int f[1000];

int climbStairs(int n){
    f[0] = f[1] = 1;              // (1)
    for(int i = 2; i <= n; ++i) {
        f[i] = f[i-1] + f[i-2];   // (2)
    }
    return f[n];
}

/*

• $(1)$ 初始化方案为 1；
• $(2)$ 你可以从 $i-1$ 层爬过来，也可以从 $i-2$ 层爬过来，所以两个方案数加和即可；
• /

斐波那切数列