【LeetCode】 Climbing Stairs – 遞迴、動態規劃

題目

思路

1. 爬樓梯，每次只能爬 1 階或 2 階。如果有N階樓梯，總共會有幾種可能呢？
2. 先從第一步開始想，第一步你可以選擇爬 1 階，也可以選擇爬 2 階
3. 如果先爬 1 階，則剩下 N – 1 階要爬。那爬 N – 1 階有幾總爬法呢？
4. 如果先爬 2 階，則剩下 N – 2 階要爬。那爬 N – 2 階有幾種爬法呢？
5. 沒錯，遞迴的味道飄出來了！爬N階的可能性，我們寫成 climbStairs(N)，則 $$climbStairs(N) = climbStairs(N-1) + climbStairs(N-2)$$
6. 奇怪，那一開始的爬 1 階和爬 2 階去哪了呢？ 其實真正的式子是這樣子的：$$climbStairs(N) = 1 \times climbStairs(N-1) + 1 \times climbStairs(N-2)$$
7. 此時我們可以寫下 解法一: 遞迴 (Recursion)
8. 哭啊！結果發現 Timeout 了！ 崩潰！
9. 我們可以用動態規劃 (dynamic programming) 來加速遞迴式
10. 此時我們可以寫下 解法二：動態規劃 (Dynamic Programming)

解法一： 遞迴 (Recursion)

class Solution:
    def climbStairs(self, n: int) -> int:
        # f(1)
        if n == 1:
            return 1

        # f(2)
        if n == 2:
            return 2

        # f(n-1) + f(n-2)
        if n >= 3: 
            return self.climbStairs(n-1) + self.climbStairs(n-2)

解法二：動態規劃 (Dynamic Programming)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2

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

筆記

• 如果對爬 1 階再爬 N -1 階和爬 2 階再爬 N – 2 階的概念不熟悉，可以參考 Leetcode 上的這個討論：https://leetcode.com/problems/climbing-stairs/discussion/comments/1570512
• 動態規劃和遞迴的關係，之後會再寫文章專門講解
• HackMD 筆記連結：https://hackmd.io/@vf2clBV9RVOcCOu5LBPT2Q/rkp7KxHOs