分析

• 本题的考点：斐波那契数列。

• 关于斐波那契数列的六种解法可以参考：斐波那契数列。

• 假设爬到第i层有f[i]种方法，则f[1] = 1, f[2] = 2，之后有f[i] = f[i-1] + f[i-2]。符合斐波那契数列的通项公式，只是初始值不同。

• 这里直接递推求解即可。

代码

• C++

class Solution {
public:
    int climbStairs(int n) {

        int a = 1, b = 1;  // b代表f[1], 我们要求f[n], 需要后移n-1次
        while (--n) {  // 会执行n-1次, b会向后移动n-1次
            int c = a + b;
            a = b, b = c;
        }
        return b;
    }
};

• Java

class Solution {
    public int climbStairs(int n) {

        int a = 1, b = 1;
        while (--n != 0) {
            int c = a + b;
            a = b; b = c;
        }
        return b;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$。

• 空间复杂度：$O(1)$。