1 題目描述

爬樓梯，每次可以爬一階或是兩階，求爬到第n階有幾種方法。

2 解法

按照之前的介紹LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南，我很推薦把每一種步驟都嘗試寫出來看看，分別是：

  1. Step1: Recursive
  2. Step2: Recursive with Memoization
  3. Step3: Iterative + Tabulation
  4. Step4: Iterative with Constant Space

Step1: Recursive

最基本也是最蠢的就是我們要先發現，基本上走樓梯的方法數量是f(n) = f(n-1) + f(n-2)，這樣的遞迴式，我們可以直接寫出來。

1
2
3
4
5
6
def climbStairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climbStairs(n-1) + climbStairs(n-2)

Step2: Recursive with Memoization

那我們就思考，是不是某些已經算過的子問題，我們可以直接拿來用，這樣就不用重複計算了。
因此我們需要一個dict來記錄已經算過的子問題。使用dict的好處是可以使用O(1)的時間複雜度來查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def climbStairs_step2(self, n: int) -> int:
    """
    time: O(n) 因為每個數字都會被計算一次
    space: O(n) 需要存儲從 1 到 n 的每個狀態
    """
    def helper(i: int) -> int:
        if i in dp:
            return dp[i]

        dp[i] = self.climbStairs_step2(i - 1) + self.climbStairs_step2(i - 2)
        return dp[i]

    dp = {1: 1, 2: 2}
    return helper(n)

Step3: Iterative + Tabulation

接下來，因為Recursive的缺點是有call stack size的限制，所以我們可以使用Iterative，來避免這個問題

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def climbStairs_step3(self, n: int) -> int:
    """
    time: O(n)
    space: O(1)
    """
    if n == 1:
        return 1
    if n == 2:
        return 2

    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

Step4: Iterative with Constant Space

最後，我們再思考一下，目前時間複雜度已經到極限了，但是空間複雜度是不是可以再省一點？因為我們只需要前面兩個步驟的結果就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def climbStairs_step4(self, n: int) -> int:
    """
    time: O(n)  因為我們只需要計算n次
    space: O(1) 只需要3個變數
    """
    if n == 1:
        return 1
    if n == 2:
        return 2
    pre_1 = 1
    pre_2 = 2
    i = 2
    while i < n:
        sumPrev = pre_1 + pre_2
        pre_1 = pre_2
        pre_2 = sumPrev
        i += 1
    return pre_2

3 結論

這題是Easy，所有的dynamic最基本的就是要先想到Recursive的解法，才可以進去DP的大門。否則一切都是空談。