LeetCode 刷題日記
EP.12

EP.12 — DP 進階：
最佳化、序列、分割

#322 Coin Change · #300 Longest Increasing Subsequence · #139 Word Break
— 三種進階 DP 模板，處理無限選擇、序列比對、字串分割

Joseph Chen

2024
5 min read
1.2k views

EP.11 打好了 1D DP 的基礎：Climbing Stairs 和 House Robber 都是「每格只依賴前一兩格」的直線型 DP。

但現實的 DP 題更複雜。有的題目允許「無限重複選同一個元素」，有的需要在序列中找到「最長遞增的子序列」，有的要判斷「字串能不能被切成字典裡的詞」。

這三種模板，對應三道 Medium，也是進階 DP 最核心的思維跳躍。

🪙

Part 1 — Coin Change

#322 · Medium · 無限揹包（Unbounded Knapsack）

題目

給一個硬幣面額陣列 coins 和目標金額 amount， 每種硬幣可以無限使用，求最少需要幾枚硬幣能湊出 amount。無解則返回 -1。

coins = [1, 5, 11], amount = 15 → 3（5+5+5）

狀態定義

dp[i] = 湊出金額 i 所需的最少硬幣數。

答案是 dp[amount]。

轉移方程

對每個金額 i，嘗試每一枚硬幣 c：

轉移方程
dp[i] = min(dp[i], dp[i - c] + 1)  # 假設你已經湊好了 i-c，再加一枚 c 就能湊到 i

Base case：dp[0] = 0（湊出 0 元需要 0 枚），其餘初始化為 float('inf')（代表「目前無法湊出」）。

可視化

coins = [1, 5, 11]，amount = 15

初始：dp[0]=0，其餘=∞

0
0
∞
1
∞
2
∞
3
∞
4
∞
5
∞
6
∞
7
∞
8
∞
9
∞
10
∞
11
∞
12
∞
13
∞
14
∞
15

填完後：dp[5]=1（一枚5），dp[10]=2（兩枚5），dp[15]=3

0
0
1
1
2
2
3
3
4
4
1
5
2
6
3
7
4
8
5
9
2
10
1
11
2
12
3
13
4
14
3
15
coin_change.py
def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for c in coins:
            if i - c >= 0:
                dp[i] = min(dp[i], dp[i - c] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1
⏱ Time: O(amount × len(coins))💾 Space: O(amount)

為什麼叫「無限揹包」？

經典揹包問題每件物品只能用一次（0/1 揹包）。這裡每種硬幣可以無限次使用，所以叫「完全揹包」或「無限揹包」。 關鍵差異在於：外層 loop 是 金額 i，內層 loop 是 每種硬幣， 因為當我們計算 dp[i] 時，dp[i-c] 已經允許用過同一枚硬幣了。

📈

Part 2 — Longest Increasing Subsequence

#300 · Medium · 序列型 DP

題目

給一個整數陣列 nums， 找出最長的嚴格遞增子序列（subsequence，不要求連續）的長度。

nums = [10, 9, 2, 5, 3, 7, 101, 18] → 4（[2, 3, 7, 101] 或 [2, 5, 7, 101]）

狀態定義

dp[i] = 以 nums[i] 為結尾的最長遞增子序列長度。

注意：這裡 dp[i] 不是「前 i 個的答案」，而是「強制把 nums[i] 當結尾」的最長長度。答案是所有 dp[i] 的最大值。

轉移方程

往回掃所有 j < i，如果 nums[j] < nums[i]，代表 nums[i] 可以接在 j 的子序列後面：

轉移方程
dp[i] = max(dp[j] + 1)  for all j < i where nums[j] < nums[i]

Base case：每個元素自成一個序列，所以 dp[i] = 1。

可視化

nums = [10, 9, 2, 5, 3, 7, 101, 18]

inums[i]dp[i]說明
0101自己一個
1919 < 10，無法接在 10 後面
2212 比前面都小，自己一個
3525 > 2，接在 dp[2]=1 後，長度 2
4323 > 2，接在 dp[2]=1 後，長度 2
5737 > 2,5,3；接在 dp[3]=2 或 dp[4]=2 後，長度 3
61014101 > 所有；接在 dp[5]=3 後，長度 4
718418 > 2,5,3,7；接在 dp[5]=3 後，長度 4

答案 = max(dp) = 4

lis.py
def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n  # 每個元素至少自成長度 1 的序列

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)
⏱ Time: O(n²)💾 Space: O(n)

🚀 進階：O(n log n) 的 Patience Sorting

面試有時會追問能不能做到 O(n log n)。答案是用「耐心排序」概念維護一個 tails 陣列，每次用 binary search 找插入位置。 但原理需要另開一篇解釋，面試前知道「有這個方法、複雜度 O(n log n)」就已足夠。

序列型 DP 的通用思路

LIS 的思路可以推廣到所有「以第 i 個元素為結尾，往前找能轉移過來的 j」的問題。 關鍵在於：dp[i] 不是「前 i 個」的最優，而是「強制以 i 結尾」的最優。 這個定義方式讓轉移方向變得清晰。

✂️

Part 3 — Word Break

#139 · Medium · 字串分割型 DP

題目

給一個字串 s 和一個字典 wordDict， 判斷 s 能否被分割成一個或多個字典裡的詞。

s = "leetcode", wordDict = ["leet","code"] → True

s = "applepenapple", wordDict = ["apple","pen"] → True

s = "catsandog", wordDict = ["cats","dog","sand","cat","an"] → False

狀態定義

dp[i] = 字串前 i 個字元（s[0:i]）能否被成功分割。

注意：dp 的長度是 len(s) + 1，因為要包含「空字串」的 Base case：dp[0] = True（空字串不需要任何詞就「可以」被分割）。

轉移方程

要判斷 dp[i]，就往前找所有切割點 j，如果 dp[j] 為 True 且 s[j:i] 在字典裡，則 dp[i] = True：

轉移方程
dp[i] = True  if dp[j] == True and s[j:i] in wordDict
                  for any j in range(0, i)

可視化

s = "leetcode", wordDict = {leet, code}

dp[0]=T空字串，Base case
dp[4]=Tj=0 → dp[0]=T，s[0:4]="leet" ∈ dict ✅
dp[8]=Tj=4 → dp[4]=T，s[4:8]="code" ∈ dict ✅
return Tdp[8] = dp[len(s)] = True

dp 陣列（i=0..8）

T
0
F
1
F
2
F
3
T
4
F
5
F
6
F
7
T
8
word_break.py
def wordBreak(s: str, wordDict: list[str]) -> bool:
    word_set = set(wordDict)  # O(1) lookup
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # 空字串可以被分割

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break  # 找到一個就夠了

    return dp[n]
⏱ Time: O(n² × w)💾 Space: O(n + |dict|)

w = 字典中最長的詞長度（字串切片的比較成本）

為什麼要把 wordDict 轉成 set？

s[j:i] in wordDict 對 list 是 O(n) 查找； 轉成 set 後變成 O(1)。 這個轉換在所有「字典查找」類 DP 題都應該是反射動作。

三種 DP 模板對比

題目dp[i] 含義轉移特點類型
Coin Change湊出金額 i 的最少硬幣每種 coin 都可以無限選，外層枚舉目標
最佳化（無限選）
LIS以 nums[i] 結尾的最長序列往前找所有合法的 j，取最大
序列比對
Word Break前 i 個字元能否分割往前找切割點 j，判斷子字串是否合法
字串分割

這三題學到什麼

🪙Coin Change：dp[i] = min(dp[i - c] + 1)，無限揹包就是「外層枚舉目標，內層枚舉選擇」
📈LIS：dp[i] 定義為「以 i 結尾」，往前找所有合法 j 取最大，是序列型 DP 的通用框架
✂️Word Break：dp[i] 代表前 i 字可分割，枚舉切割點 j，轉移依賴 dp[j] + 字典查找
⚡字典查找務必轉成 set；dp 長度是 amount+1 或 len(s)+1，不要少一格

上一篇

EP.11 — DP 入門

Climbing Stairs、House Robber

下一篇

敬請期待

Graph、Backtracking...

LeetCode
DP
Python
Coin Change
LIS
Word Break
EP.12