← All notes
LeetCode Cycle 12 & 13：DP 五步法、背包、股票、LCS、編輯距離
DP 在面試桌前被當「決定生死」的題型——不是難在邏輯而是難在「看不出來是 DP」。Senior 面試看你能不能 30 秒內判定：這題有沒有重疊子問題＋最優子結構？有就 DP，沒有就 backtracking。Cycle 12 & 13 把 5 步法、背包、股票、LCS、編輯距離串成一張命題網。內部使用。
DP 跟 backtracking 同源——都是「樹形搜索」——但 DP 多了兩個必要條件[^1]：
- 重疊子問題（overlapping subproblems）：子問題重複出現，所以可以 cache
- 最佳子結構（optimal substructure）：原問題的最佳解可以由子問題的最佳解組合
少了 1，cache 沒意義（每個子問題只算一次）→ 退化成 backtracking；少了 2，子問題最佳解組不出原問題最佳解 → 根本不能用 DP。面試官追問「為什麼這題能用 DP」答案就是這兩條。
下面用代码随想录的 5 步驟法（狀態定義 → 轉移方程 → 初始化 → 遍歷順序 → 舉例驗證）走遍 4 個招牌模板。