動態規劃核心：5 題用同一套框架打通 DP（LC 70/198/322/300/1143）

很多人覺得 DP 是「靈光一閃」型的題目——其實正好相反。DP 是最有固定套路的主題，套路就是這五步：

① 定義狀態（dp[i] 是什麼）→ ② 寫轉移方程（dp[i] 怎麼從更小的算出來）→ ③ base case → ④ 計算順序 → ⑤ 答案在哪

只要這五步填得出來，code 幾乎是自動長出來的。難的從來不是寫迴圈，而是**「dp[i] 到底代表什麼」**——狀態定義對了，轉移就自然浮現。

這篇用 5 題把這套框架練到反射，延續一貫的完整推導流程：

📋 題目 → 🧭 拆解 → 暴力 → 瓶頸 → 洞察 → 最優 → 程式碼

• 線性遞推（70 爬樓梯）→ 帶選擇的遞推（198 打家劫舍）→ 最優化湊數（322 零錢兌換）→ 子序列 DP（300 LIS、1143 LCS）

① LC 70 — Climbing Stairs

📋 題目：爬 n 階樓梯，每次可爬 1 或 2 階，問有幾種不同的爬法。

範例：n = 2 → 2（1+1、2）；n = 3 → 3（1+1+1、1+2、2+1）

🌐 EN — Climbing n stairs, each step you can climb 1 or 2 steps; how many distinct ways to reach the top? Example: n = 2 → 2; n = 3 → 3

🧭 從讀題到解法

1. 拆解：要到第 n 階，最後一步要嘛從 n-1 跨 1 階、要嘛從 n-2 跨 2 階。所以到 n 的爬法 = 到 n-1 的爬法 + 到 n-2 的爬法。
2. 套框架：
   • 狀態：dp[i] = 爬到第 i 階的方法數。
   • 轉移：dp[i] = dp[i-1] + dp[i-2]（就是 Fibonacci）。
   • base case：dp[1] = 1, dp[2] = 2。
   • 順序：i 由小到大。答案：dp[n]。
3. 最優解：只需記住前兩個值，用兩個變數滾動，空間 O(1)。

def climbStairs(n):
    if n <= 2:
        return n
    a, b = 1, 2                    # ways to reach step 1, step 2
    for _ in range(3, n + 1):
        a, b = b, a + b            # roll forward
    return b

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b; b = c;
    }
    return b;
}

• 複雜度：時間 O(n)，空間 O(1)。
• 坑：① 這就是 Fibonacci，認出來就秒解；② 用滾動變數省掉整個 dp 陣列；③ 想清楚是「最後一步從哪來」——這是所有線性 DP 的起手式。

② LC 198 — House Robber

📋 題目：一排房子各有金額 nums[i]，不能搶相鄰兩間（會觸發警報）。求能搶到的最大金額。

範例：nums = [1,2,3,1] → 4（搶 1+3）；nums = [2,7,9,3,1] → 12（搶 2+9+1）

🌐 EN — Houses in a row with amounts nums[i]; you can't rob two adjacent houses. Return the max amount you can rob. Example: [1,2,3,1] → 4; [2,7,9,3,1] → 12

🧭 從讀題到解法

1. 拆解：到第 i 間，你面臨二選一：搶它（就不能搶 i-1，金額 = dp[i-2] + nums[i]），或不搶它（金額 = dp[i-1]）。取較大。
2. 套框架：
   • 狀態：dp[i] = 考慮前 i 間能搶到的最大金額。
   • 轉移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])（不搶 vs 搶）。
   • base case：dp[0] = nums[0]、dp[1] = max(nums[0], nums[1])。
   • 答案：dp[n-1]。
3. 關鍵洞察：DP 的精髓是「在每個狀態做最優選擇」——這題的「搶 / 不搶」就是經典的選擇型轉移。
4. 最優解：滾動兩個變數即可。

def rob(nums):
    prev, curr = 0, 0              # best up to i-2, up to i-1
    for n in nums:
        prev, curr = curr, max(curr, prev + n)   # skip vs rob
    return curr

int rob(vector<int>& nums) {
    int prev = 0, curr = 0;
    for (int n : nums) {
        int next = max(curr, prev + n);   // skip vs rob
        prev = curr; curr = next;
    }
    return curr;
}

• 複雜度：時間 O(n)，空間 O(1)。
• 坑：① 轉移是「不搶（繼承 dp[i-1]）vs 搶（dp[i-2]+nums[i]）」，別漏了「不搶」這支；② 用 prev/curr 兩變數時，初始都設 0 很乾淨；③ 進階版 213（環形）只要把首尾拆成兩次線性 DP。

③ LC 322 — Coin Change

📋 題目：給定硬幣面額 coins（每種可用無限次）與目標金額 amount，求湊出 amount 的最少硬幣數；湊不出回 -1。

範例：coins = [1,2,5], amount = 11 → 3（5+5+1）；coins = [2], amount = 3 → -1

🌐 EN — Given coin denominations coins (each usable unlimited times) and a target amount, return the fewest coins to make amount, or -1 if impossible. Example: coins = [1,2,5], amount = 11 → 3; coins = [2], amount = 3 → -1

🧭 從讀題到解法

1. 拆解：要湊 amount，最後一枚硬幣若是 coin，那剩下的就是「湊 amount - coin 的最少硬幣數」+ 1。試所有 coin 取最小。
2. 錯誤的直覺：貪心「每次拿最大面額」——反例：coins=[1,3,4], amount=6，貪心拿 4+1+1=3 枚，但最優是 3+3=2 枚。貪心在任意面額下不對，得用 DP。
3. 套框架：
   • 狀態：dp[a] = 湊出金額 a 的最少硬幣數。
   • 轉移：dp[a] = min(dp[a - coin] + 1) 對所有 coin <= a。
   • base case：dp[0] = 0（湊 0 元用 0 枚）。
   • 答案：dp[amount]，若仍是無限大則 -1。
4. 最優解：自底向上填 dp 陣列。

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);   // amount+1 as "infinity"
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int coin : coins)
            if (coin <= a)
                dp[a] = min(dp[a], dp[a - coin] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

• 複雜度：時間 O(amount × len(coins))，空間 O(amount)。
• 坑：① 不要用貪心（任意面額會錯）；② 用「無限大」初始化（C++ 用 amount+1 當哨兵避免溢位），最後判斷是否還是無限大決定回 -1；③ 這是「完全背包（硬幣可重複用）求最小」的模板，認得出來就通殺一類題。

④ LC 300 — Longest Increasing Subsequence

📋 題目：給定整數陣列 nums，回傳最長嚴格遞增子序列的長度（子序列不需連續）。

範例：nums = [10,9,2,5,3,7,101,18] → 4（2,3,7,101）；nums = [0,1,0,3,2,3] → 4

🌐 EN — Given an integer array nums, return the length of the longest strictly increasing subsequence (not necessarily contiguous). Example: [10,9,2,5,3,7,101,18] → 4; [0,1,0,3,2,3] → 4

🧭 從讀題到解法

1. 拆解：子序列、求最長——典型 DP。難點在狀態怎麼定。
2. 關鍵：狀態要「以 i 結尾」。若 dp[i] 定義成「前 i 個的 LIS」會難以轉移；改成「以 nums[i] 結尾的 LIS 長度」就好接：
   • 狀態：dp[i] = 以 nums[i] 結尾的最長遞增子序列長度。
   • 轉移：dp[i] = max(dp[j] + 1) 對所有 j < i 且 nums[j] < nums[i]；沒有就 dp[i] = 1。
   • 答案：max(dp)（不是 dp[n-1]，因為最長的可能在中間結尾）。
3. 最優解（O(n²)）：雙層迴圈。

def lengthOfLIS(nums):
    dp = [1] * len(nums)              # each element alone is length 1
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

int lengthOfLIS(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    for (int i = 0; i < (int)nums.size(); i++)
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i])
                dp[i] = max(dp[i], dp[j] + 1);
    return *max_element(dp.begin(), dp.end());
}

💡 進階：O(n log n) 耐心排序（patience sorting）

import bisect
def lengthOfLIS(nums):
    tails = []                       # tails[k] = smallest tail of an LIS of length k+1
    for n in nums:
        i = bisect.bisect_left(tails, n)
        if i == len(tails):
            tails.append(n)
        else:
            tails[i] = n             # keep tails as small as possible
    return len(tails)

tails 維護「長度 k 的遞增子序列中，最小的結尾值」，用二分插入，整體 O(n log n)。

• 複雜度：DP O(n²)；patience O(n log n)；空間 O(n)。
• 坑：① 狀態要「以 i 結尾」才好轉移；② 答案是 max(dp) 不是 dp[-1]；③ 「嚴格遞增」用 <，若改成「非遞減」要用 bisect_right。

⑤ LC 1143 — Longest Common Subsequence

📋 題目：給定兩字串 text1、text2，回傳它們最長公共子序列的長度（子序列不需連續，但要保持相對順序）。

範例：text1 = "abcde", text2 = "ace" → 3（"ace"）；"abc", "def" → 0

🌐 EN — Given strings text1, text2, return the length of their longest common subsequence (not contiguous, but order-preserving). Example: "abcde", "ace" → 3; "abc", "def" → 0

🧭 從讀題到解法

1. 拆解：兩個字串、求公共——典型二維 DP。狀態自然是「兩個字串各看到哪」。
2. 套框架：
   • 狀態：dp[i][j] = text1 前 i 個字元與 text2 前 j 個字元的 LCS 長度。
   • 轉移：
     • 若 text1[i-1] == text2[j-1]（末字元相同）→ dp[i][j] = dp[i-1][j-1] + 1。
     • 否則 → dp[i][j] = max(dp[i-1][j], dp[i][j-1])（丟掉其一的末字元）。
   • base case：dp[0][*] = dp[*][0] = 0（空字串）。
   • 答案：dp[m][n]。
3. 關鍵洞察：二維 DP 的精髓是「末字元相不相同」這個分岔——相同就一起 +1、不同就退一格取較大。LCS 是這類「雙序列 DP」的母題（編輯距離、最短公共超序列都是它的變形）。

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (text1[i-1] == text2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    return dp[m][n];
}

• 複雜度：時間 O(m·n)，空間 O(m·n)（可滾動成 O(n)）。
• 坑：① dp 開 (m+1)×(n+1)，多一圈處理空字串 base case；② 字串索引 text[i-1] 對應 dp[i]，差一別搞混；③ 末字元不同時是 max(上, 左)，不是 dp[i-1][j-1]。

DP 五步框架（一張表收束）

面試辨識口訣

• 看到「有幾種方法 / 走到終點」→ 線性 DP，想「最後一步從哪來」。
• 看到「選或不選、相鄰限制」→ 選擇型轉移 max(選, 不選)。
• 看到「湊出目標、最少/最多用幾個」→ 背包型 DP（別用貪心）。
• 看到「最長/最短子序列」→ 狀態定義成「以 i 結尾」。
• 看到「兩個字串/序列」→ 二維 DP，分岔在「末元素相不相同」。

DP 的精髓不是背題,而是把「五步框架」變成反射:先問 dp[i] 是什麼,再問它怎麼從更小的算出來。狀態定義對了,這題就解一大半。