題目網址：https://leetcode.cn/problems/climbing-stairs/

題意：今天有 n 階樓梯要爬, 每一次你可以選擇要爬 1階 or 2階, 求總共有幾種不同的爬法。

Solution 1：（TLE 無法通過）

想法：利用遞迴求解

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};

time complexity 證明：

T(n) = T(n - 1) + T(n - 2) + c
     <= 2T(n - 1) + c, 取 upper bound T(n - 2) <= T(n - 1)
      = 2*(2T(n - 2) + 1) + (1 * c)
      = 4T(n - 2) + (2 * c)
      = 8T(n - 3) + (3 * c)
      = 2^k * T(n - k) + (2^k * c)

令 k = n , T(0) = 1
T(n) <= 2^n * T(0) + (2^n * c)
      = 2^n * (1 + c)

  • time：$O(2^n)$

  • space：$O(n)$ ➔ 受限於 tree 的深度, 下圖中可以看到 F(6) 的深度 = 6 - 1 = n - 1

    遞迴缺點：重複計算, e.g. 上圖中可看到 F(3) 被重複呼叫好幾次

Solution 2：

想法：利用 DP, 紀錄 0, 1, 2, …, n 階的方法數, 用空間換取時間, 避免重複計算

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 1);
        for (int i = 2; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp.back();
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(n)$ ➔ dp

Solution 3：

想法：改進 Solution 2, dp[i] = dp[i - 1] + dp[i - 2] 中 dp[i] 只會用到前兩步的方法數, 也就是說只需紀錄 dp[i - 1] 和 dp[i - 2] 就好, 根本不需要開到 n 個空間

class Solution {
public:
    int climbStairs(int n) {
        int one = 1; // dp[i - 1]
        int two = 1; // dp[i - 2]

        for (int i = 2; i <= n; ++i) {
            int cur = one + two; // dp[i]
            two = one;
            one = cur;
        }

        return one;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ 只需常數空間