思路

1. $f_i$表示到达第i级时的方案数.
2. $f_i$只能是跳1步和跳2步到达, 也就是由$f_{i-1} + f_{i-2}$确定
3. 可以通过两个变量保存中间状态, f3 = f1 + f2; f1 = f2; f2 = f3. 确保$O(1)$的空间

代码

class Solution {
    public int climbStairs(int n) {
         //这是一个动态规划的题
        if(n < 2) return 1;
        int f1 = 1, f2 = 1, f3 = f1 + f2;
        while(n-- > 1){
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
}