LeetCode 刷題日記
EP.11

Dynamic Programming
把大問題拆成子問題，然後記住答案

#70 Climbing Stairs · #198 House Robber — 用兩題打通 1D DP 的思維

Joseph Chen
2024
Back to Blog
5 min read
1.2k views

Dynamic Programming（DP）是很多人覺得最難的主題，但它的核心其實只有兩件事：① 找到子問題的結構，② 把子問題的答案存起來避免重複計算。這篇用 Climbing Stairs 和 House Robber 兩道經典題，從「為什麼遞迴會超時」出發，解釋 DP 的必要性。

DP 解決的問題類型

DP 適用於「最優子結構」的問題：大問題的最優解可以由子問題的最優解推導出來，而且子問題之間有重疊。

🔁

重疊子問題

同樣的子問題被計算多次

🏆

最優子結構

大問題的最優解包含子問題的最優解

💾

記憶化

子問題算過就存起來，避免重複

#70 Climbing Stairs

爬 n 階樓梯，每次可以爬 1 階或 2 階，有幾種方法？

範例
n = 3
→ 3 種：(1+1+1)、(1+2)、(2+1)

n = 4
→ 5 種：(1+1+1+1)、(1+1+2)、(1+2+1)、(2+1+1)、(2+2)

先嘗試暴力遞迴的思維：到達第 n 階，只可能從第 n-1 階跨一步上來，或從第 n-2 階跨兩步上來。所以：

climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)
暴力遞迴 — 正確但超時 O(2ⁿ)
def climbStairs(n):
    if n <= 2:
        return n
    return climbStairs(n - 1) + climbStairs(n - 2)

# 問題：climbStairs(5) 的呼叫樹：
# climbStairs(5)
# ├─ climbStairs(4)
# │   ├─ climbStairs(3)  ← 重複計算！
# │   └─ climbStairs(2)
# └─ climbStairs(3)      ← 重複計算！
#     ├─ climbStairs(2)
#     └─ climbStairs(1)

子問題大量重複計算，指數級爆炸。解法：把算過的答案存起來（Memoization），或由小到大填表（Tabulation）。

解法一：Top-Down Memoization（遞迴 + 快取）

Top-Down
def climbStairs(n: int) -> int:
    memo = {}

    def dp(i):
        if i <= 2:
            return i
        if i in memo:       # 算過就直接回傳
            return memo[i]
        memo[i] = dp(i - 1) + dp(i - 2)
        return memo[i]

    return dp(n)

解法二：Bottom-Up Tabulation（由小到大填表）

Bottom-Up
def climbStairs(n: int) -> int:
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1   # 1 階有 1 種方法
    dp[2] = 2   # 2 階有 2 種方法

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # 狀態轉移方程

    return dp[n]
⏱ Time: O(n)💾 Space: O(n)

n=6 時的填表過程：

1
dp[1]
2
dp[2]
3
dp[3]
5
dp[4]
8
dp[5]
13
dp[6]

每格 = 前兩格相加。這其實就是 Fibonacci 數列！

解法三：空間優化（只需保留前兩個值）

Space O(1)
def climbStairs(n: int) -> int:
    if n <= 2:
        return n

    prev2, prev1 = 1, 2   # dp[1], dp[2]

    for _ in range(3, n + 1):
        curr  = prev1 + prev2
        prev2 = prev1
        prev1 = curr

    return prev1
⏱ Time: O(n)💾 Space: O(1)

DP 的解題框架

1
定義狀態：dp[i] 代表什麼？（通常是「到第 i 個位置為止，某個問題的最優答案」）
2
找出狀態轉移方程：dp[i] 和 dp[i-1]、dp[i-2]... 之間的關係是什麼？
3
初始化 base case：dp[0]、dp[1] 等邊界值是什麼？
4
決定計算順序：通常由小到大（確保算 dp[i] 時，依賴的子問題都已計算完）
5
回傳答案：通常是 dp[n] 或 dp 陣列中的最大/最小值

#198 House Robber

一排房子，每間有不同金額。你不能搶相鄰的兩間（會觸發警報），求能搶到的最大金額。

範例
nums = [2, 7, 9, 3, 1]
→ 12：搶 index 0(2) + index 2(9) + index 4(1)

nums = [1, 2, 3, 1]
→ 4：搶 index 0(1) + index 2(3)

套入 DP 框架：

狀態定義dp[i] = 搶到第 i 間房子為止，能得到的最大金額
轉移方程dp[i] = max(dp[i-1], dp[i-2] + nums[i])，要麼跳過這間，要麼搶這間（就不能搶前一間）
Base casedp[0] = nums[0]（只有一間，直接搶） dp[1] = max(nums[0], nums[1])（兩間取較大的）
#198 House Robber
class Solution:
    def rob(self, nums: list[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, len(nums)):
            # 選擇一：跳過這間（繼承前一間的最大值）
            # 選擇二：搶這間（前兩間的最大值 + 這間）
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

        return dp[-1]
⏱ Time: O(n)💾 Space: O(n)

nums = [2, 7, 9, 3, 1] 的填表過程：

inums[i]dp[i-2]+nums[i]dp[i-1]dp[i]
02——2
17—27
292+9=11711
337+3=101111
4111+1=121112 ✅

空間優化版（同樣的 O(1) 技巧）：

Space O(1)
class Solution:
    def rob(self, nums: list[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        prev2 = nums[0]
        prev1 = max(nums[0], nums[1])

        for i in range(2, len(nums)):
            curr  = max(prev1, prev2 + nums[i])
            prev2 = prev1
            prev1 = curr

        return prev1
⏱ Time: O(n)💾 Space: O(1)

兩題的共同模式

Climbing Stairs 和 House Robber 看起來不一樣，但轉移方程的結構幾乎相同：

題目dp[i] 定義轉移方程
Climbing Stairs爬到第 i 階的方法數dp[i] = dp[i-1] + dp[i-2]
House Robber搶到第 i 間的最大金額dp[i] = max(dp[i-1], dp[i-2]+nums[i])

兩者的核心都是：dp[i] 只依賴 dp[i-1] 和 dp[i-2]，因此都可以用兩個變數把空間壓到 O(1)。這個優化技巧幾乎適用所有 1D DP。

DP 最難的不是寫程式，而是想出「狀態定義」和「轉移方程」。只要這兩件事清楚，程式幾乎自己寫出來。每次看到 DP 題，先問：「dp[i] 代表什麼，它和更小的子問題之間的關係是什麼？」

本篇重點整理

🧩DP = 把大問題拆成子問題，存起來避免重複計算
📋五步框架：狀態定義 → 轉移方程 → Base case → 計算順序 → 回傳答案
🪜Climbing Stairs：dp[i] = dp[i-1] + dp[i-2]，本質是 Fibonacci
🏠House Robber：dp[i] = max(跳過, 搶這間)，兩個選擇取最大
💡只依賴前兩個 dp 值時，用兩個變數把 O(n) 空間壓到 O(1)

上一篇

EP.10 — Tree BFS & BST

層序遍歷、驗證 BST、找共同祖先

下一篇

EP.12 — DP 進階

Coin Change、LIS、Word Break

LeetCode
DP
Python
1D DP
EP.11