算法

(DP) $O(n)$

非常基础的动态规划入门题。
对于每个$n$级台阶来说只有两种选择：第一种选择是最后一次爬了一级台阶到达了第$n$级，方法数就是$f(n-1)$；同理如果最后爬了两级台阶到达了第$n$级，方法数就是$f(n-2)$。所以状态转移方程就是$f(n)=f(n-1)+f(n-2)$。
边界条件：$f(0)=1$表示只有$0$级台阶需要爬，所以可选择不爬；$f(1)=1$表示只有$1$级台阶需要爬，所以最后一个台阶只能选择爬$1$级。

Java 代码

class Solution {
    public int climbStairs(int n) {
        // f(n): 爬完n级的方法数
        // f(n) = f(n - 1) + f(n - 2)  
        // f(0) = 1, f(1) = 1
        int prev1 = 1;
        int prev2 = 1;
        for (int i = 2; i <= n; ++i) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

Python 代码

class Solution:
    def climbStairs(self, n: int) -> int:
        dp1, dp2 = 1, 2
        for i in range(n - 1):
            dp1, dp2 = dp2, dp1 + dp2
        return dp1