動態規劃實戰指南#
動態規劃是模板、套路屆的典範。掌握解題框架後，再加上適當的練習，就能輕鬆攻破技術面試中的 DP 難關。本節整理 DP 題目的分類、解題框架和刷題建議。
解題框架回顧#
動態規劃五步曲#
1. 判斷是否為 DP 問題
└── 檢查三要素：重叠子問題、無後效性、最優子結構
2. 確定狀態定義
└── DP[i] 或 DP[i][j] 代表什麼含義
3. 確定初始化狀態
└── 計算的原點，邊界條件
4. 確定狀態參數
└── 會發生變化的變數
5. 確定狀態轉移方程
└── 當前狀態如何從子問題推導
6. 確定計算方向
└── 確保依賴的狀態已計算
7. 考慮空間優化
└── 滾動陣列、狀態壓縮核心原則 一旦寫出狀態轉移方程，問題就解決了一大半。 方程的正確性來源於對「最優子結構」的理解。
判斷是否為 DP 問題#
| 問題類型 | 特徵 | 典型問法 |
|---|---|---|
| 求最優解 | 含「最」字 | 最長、最短、最大、最小 |
| 求可行性 | 問「能否」 | 能否達成、是否可行 |
| 求方案數 | 問「多少種」 | 有多少種方法、組合數量 |
題目分類#
一、線性問題#
最基礎的 DP 類型，按問題規模從小到大推導。
| 題目 | 難度 | 狀態定義 |
|---|---|---|
| 爬樓梯 | 簡單 | dp[i] = 到達 i 的方法數 |
| 打家劫舍 | 中等 | dp[i] = 前 i 間房的最大金額 |
| 最大子陣列和 | 中等 | dp[i] = 以 i 結尾的最大和 |
| 最長上升子序列 | 中等 | dp[i] = 以 i 結尾的最長長度 |
| 零錢兌換 | 中等 | dp[i] = 湊成 i 的最少硬幣數 |
初學建議 從線性問題開始練習，不斷加深對 DP 的理解。 掌握後再學習其他類型，會事半功倍。
二、區間問題#
使用多個狀態參數約束資料結構訪問範圍。
| 題目 | 難度 | 狀態定義 |
|---|---|---|
| 最長回文子序列 | 中等 | dp[i][j] = s[i..j] 的最長回文長度 |
| 戳氣球 | 困難 | dp[i][j] = 戳破 (i,j) 區間的最大硬幣 |
| 最長回文子串 | 中等 | dp[i][j] = s[i..j] 是否回文 |
區間問題的特點：
- 需要兩個狀態參數（區間端點）
- 狀態轉移按區間長度從短到長
- 要特別注意計算方向
線性問題：DP[i] 依賴 DP[i-1]，從左到右計算
區間問題：DP[i][j] 可能依賴 DP[i+1][j-1]，需要反向計算三、背包問題#
組合優化的 NP 完全問題。
| 題目 | 類型 | 關鍵特徵 |
|---|---|---|
| 0-1 背包 | 經典 | 每種物品只有 1 個 |
| 完全背包 | 經典 | 每種物品無限個 |
| 多重背包 | 進階 | 每種物品有 k 個 |
| 分割等和子集 | 變種 | 轉化為 0-1 背包 |
| 目標和 | 變種 | 轉化為背包問題 |
面試提醒 面試中很少直接考察標準背包問題，更多的是考察變種。 關鍵是識別出背包問題的特徵並進行轉化。
四、方案總數問題#
| 題目 | 難度 | 說明 |
|---|---|---|
| 不同路徑 | 簡單 | 從左上到右下的路徑數 |
| 不同路徑 II | 中等 | 帶障礙物的路徑數 |
| 組合總和 IV | 中等 | 湊成目標的組合數 |
五、複雜問題#
面試中常考的高難度 DP 問題。
| 題目 | 難度 | 備註 |
|---|---|---|
| 編輯距離 | 困難 | 字串匹配必修題 |
| 股票買賣系列 | 中等-困難 | 多狀態 DP |
| 正則表達式匹配 | 困難 | 字串 DP |
| 最長公共子序列 | 中等 | 雙字串 DP |
備忘錄設計技巧#
維度選擇#
狀態參數數量 → 備忘錄維度
1 個參數（如位置 i）→ 一維陣列 dp[i]
2 個參數（如區間 i,j）→ 二維陣列 dp[i][j]
3 個參數（如天數、交易次數、持有狀態）→ 三維陣列 dp[i][k][j]定義方式#
| 問題類型 | 常用定義 |
|---|---|
| 子陣列問題 | dp[i] = 以 i 結尾的最優解 |
| 子序列問題（單串） | dp[i][j] = 區間 [i,j] 的最優解 |
| 子序列問題（雙串） | dp[i][j] = 前綴 [0,i] 和 [0,j] 的最優解 |
| 背包問題 | dp[i][w] = 前 i 個物品、容量 w 的最優解 |
空間優化技巧#
若 dp[i] 只依賴 dp[i-1]：
→ 使用兩個變數替代陣列
若 dp[i][j] 只依賴當前行和上一行：
→ 使用滾動陣列（兩行）
若 dp[i][j] 只依賴左邊和上邊：
→ 可以壓縮到一維陣列計算方向總結#
常見錯誤 計算方向錯誤會導致依賴的子問題尚未計算，結果錯誤。
判斷方法#
- 找出當前狀態依賴哪些更小的子問題
- 確定最終結果的存儲位置
- 確保從「已知」推向「未知」
常見模式#
| 依賴關係 | 計算方向 |
|---|---|
dp[i] 依賴 dp[i-1] | i 從小到大 |
dp[i] 依賴 dp[i+1] | i 從大到小 |
dp[i][j] 依賴 dp[i-1][j-1] | i, j 從小到大 |
dp[i][j] 依賴 dp[i+1][j-1] | i 從大到小，j 從小到大 |
刷題建議#
學習路線#
第一階段：線性問題
├── 爬樓梯
├── 打家劫舍
├── 最大子陣列和
└── 最長上升子序列
第二階段：背包問題
├── 0-1 背包
├── 完全背包
├── 分割等和子集
└── 零錢兌換
第三階段：區間與子序列
├── 最長回文子序列
├── 最長公共子序列
└── 編輯距離
第四階段：多狀態 DP
├── 股票買賣系列
├── 打家劫舍 II、III
└── 跳躍遊戲系列練習方法#
高效練習法
- 理解 > 死記：理解狀態定義和轉移邏輯，而非死記程式碼
- 手動模擬：用紙筆填充 DP 表格，理解計算過程
- 變體練習：做完一題後，思考如何解決變種問題
- 總結歸類：按題目類型建立自己的解題筆記
面試策略#
先確認問題類型
- 看問題的問法（最優解、可行性、方案數）
- 識別是否為經典問題的變種
明確狀態定義
- 用清晰的語言描述
dp[i]的含義 - 確定需要幾個維度
- 用清晰的語言描述
寫出狀態轉移方程
- 先用數學公式表達
- 考慮邊界條件
確定計算方向和初始化
- 畫出依賴關係圖
- 確保初始狀態正確
討論優化空間
- 時間複雜度是否可以優化
- 空間是否可以壓縮
常見陷阱#
1. 狀態定義不當#
錯誤：dp[i] = 陣列 [0..i] 中的最大子陣列和
問題：無法保證與 nums[i+1] 連續
正確：dp[i] = 以 i 結尾的最大子陣列和
2. 初始化錯誤#
錯誤：全部初始化為 0 問題：可能影響求最大值的邏輯
正確：根據問題語義初始化（如 -∞ 或 amount+1）
3. 計算方向錯誤#
錯誤：總是從左上到右下填表 問題：某些問題需要反向計算
正確：根據依賴關係確定計算方向
4. 索引越界#
錯誤：直接訪問 dp[i-1] 而不檢查 i > 0
正確：先處理邊界情況，或多開一行/列
總結#
動態規劃的本質
- DP 不是一種演算法，而是一種解決問題的思想
- 核心是利用已計算的結果推導新結果
- 關鍵是找到正確的狀態定義和轉移方程
學習心態：
- 初期：多看、多練、多反覆，將解法邏輯內化
- 中期：形成自己的解題框架，舉一反三
- 進階：能識別新問題與經典問題的聯繫，靈活轉化
動態規劃問題總共就那麼多種類型，只要掌握解題框架並適當練習，就能輕鬆應對面試中的 DP 難關。