Leetcode 70. Climbing Stairs

這是一題關於 Dynamic Programming, DP 的問題
就是把一個問題拆成多個子問題一直拆解下去

題目是這樣：
爬梯子，最多只能腳跨 1 格或是 2 格（腳不夠長）
階梯有 n 階，你最多有多少方式可以跨完

範例是：

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

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 - 1, n - 2

假設是 5 階
我若走 1 階就還剩 4 階 ( 5 - 1 )
我若走 2 階就還剩 3 階 ( 5 - 2 )

無論我前面走了多少階層，我剩 3 階的步數都一樣 (只是舉個數字範例，這裡可以是 x

例如:
我總共 8 階，我走到剩下 3 階的時候就代表我剩下 3 種解法 （看範例）
我總共 19231092830 階，我走到剩下 3 階的時候就代表我剩下 3 種解法

所以我們可以從前面開始算，接著我們把它存到 dp 裡面就不用重複計算
不論你在第幾階，你就是前面的所有組合相加

爬到第 2 階有 2 種方法
爬到第 3 階有 3 種方法
爬到第 4 階有 5 種方法
爬到第 5 階有 8 種方法

所以現在假設 n = 5

1. 我走 1 階 → 剩下 4 階 = 5 種
2. 我走 2 階 → 剩下 3 階 = 3 種

5 + 3 = 8 種 （算過的我們就不再算了）

下面圖解隨便看

DP 的關係式：

dp[i] = 爬到第 i 階的方法數

# 爬到地 i 階就是
從第 i - 1 階跨 1 階上來
從第 i - 2 階跨 2 階上來

# 簡單來來說核心就是
dp[i] = dp[i - 1] + dp[i - 2]

# 初始化
dp[1] = 1
dp[2] = 2​

# 算階層
dp[1] = 1
dp[2] = 2
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8​

這是我的，但我覺得我的寫法可以在優化，我沒有特別想

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1: return 1
        elif 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 - 2] + dp[i - 1]
            print(f"dp[{i}] = {dp[i - 2]} + {dp[i - 1]} = {dp[i]}")

        return dp[n]

P.S. 方格子寫這些格式好難調整，一直壞掉有人知道是爲什麼嗎？寫起來有點不順