70. Climbing Stairs

  • Hardness: \(\color{green}\textsf{Easy}\)
  • Ralated Topics: Math、Dynamic Programming、Memoization

一、題目

You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

  • Input: n = 2
  • Output: 2
  • Explanation: There are two ways to climb to the top.
  1. 1 step + 1 step
  2. 2 steps

Example 2:

  • Input: n = 3
  • Output: 3
  • Explanation: There are three ways to climb to the top.
  1. 1 step + 1 step + 1 step
  2. 1 step + 2 steps
  3. 2 steps + 1 step

Constraints:

  • 1 <= n <= 45

二、分析

  • 經典的動態規劃問題，因為只有 1-step 與 2-steps 兩個選擇，所以 n 階的樓梯的走法會是 n-1 階與 n-2 階走法的總和。
  • 令 n 階走法的數目為 dp[n]，dp[n] = dp[n-1] + dp[n-2]。
  • 注意初始條件 dp[0] = 1，dp[1] = 1。
  • 可以發現此為費式數列，即 1,1,2,3,5,8,13,21...。

三、解題

1. DP

  • Time complexity: \(O()\)
  • Space complexity: \(O()\)
int climbStairs(int n) {
    int dp[n+1];
    dp[0] = 1, dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

回目錄 Catalog