70. Climbing Stairs

Leetcode

https://leetcode.com/problems/climbing-stairs/description/

題目

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

解答

• 方法一 - 遞迴

因為每次只能走 1 步或 2 步，所以到達第 n 個步驟所走的可能性，其實就是 第 n - 1 個步驟的可能性 + 第 n - 2 個步驟的可能性，兩種方式加起來的數量

var climbStairs = function(n) {
    if (n === 1) {
        return 1;
    }
    if (n === 2) {
        return 2;
    }

    return climbStairs(n - 1) + climbStairs(n - 2);
};

但很可惜的是這個解法在 n = 44 時會是 TLE...，原因是當計算 climbStairs(43) + climbStairs(42) 時，42 會從 1~42 一路計算，而 43 也會從 1~43 一路計算，其中 1~42 計算的部分就重複了

時間複雜度：O(2^n)

原因：
每一輪一直往下算的話都會 * 2 倍的計算量，所以時間複雜度會是 2^n

n = 4          *
n = 3      *       *
n = 2    *   *   *   *
n = 1   * * * * * * * *

• 方法二 - 遞迴 + cache

為了解決方法一的重複計算我們可以用 cache 的方式，記錄每一輪 n 計算的結果，以優化計算速度

var climbStairs = function(n, memo = {}) {
    if (n === 1) {
        memo[1] = 1;
        return 1;
    }
    if (n === 2) {
        memo[2] = 2;
        return 2;
    }
    if (memo[n]) {
        return memo[n];
    }

    const result = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
    memo[n] = result;

    return result;
};

• 方法三 - DP

按照上面遞迴的思路，只是我們現在直接用一個矩陣保存每一輪 n 的結果

var climbStairs = function (n) {
    const dp = [1, 2];

    for (let i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n - 1];
};

時間複雜度：O(n)

空間複雜度：O(n)

• 方法四 - DP 優化空間

從上面可以知道，要求得第 n 個 steps 所有可能走到的方式關鍵就是 n - 1 步驟 + n - 2 步驟的總數，而方法三中的 dp 矩陣保存著每一輪 n 的結果，為了更優化空間複雜度可以只保留 n - 1 步驟的結果及 n - 2 步驟的結果就好

var climbStairs = function (n) {
    if (n === 1) return 1;
    if (n === 2) return 2;

    let last2 = 1; // n-2 步驟的總數
    let last = 2; // n-1 步驟的總數
    let result;

    for (let i = 3; i <= n; i++) {
        result = last2 + last;
        // 將 n-2 的結果替換成 n-1 的結果
        last2 = last;
        // 將 n-1 的結果替換成當輪計算的結果
        last = result;
    }

    return result;
};

時間複雜度：O(n)

空間複雜度：O(1)

參考資料

70. Climbing Stairs · leetcodeleetcode.wang