🎯 什麼情境該想到我
分工：這張是「看到題目，辨認該用哪個策略」的分類卡。各策略的機制、證明、程式碼 → 分治法、貪婪演算法、動態規劃；具體演算法 →
reference/演算法導論/。
當你面對一個計算/最佳化問題、暴力解太慢、想不到更好解法時。先辨認它屬於哪種策略。
⚙️ 怎麼用（辨認問題型態 → 套對應策略）
- 分治（Divide & Conquer）：能把問題拆成同型的小問題、各自解完再合併 → 如合併排序、快排、二分。
- 貪婪（Greedy）：每一步都取「當下看起來最好」的選擇即可得全域最佳 → 如區間排程、Huffman。（要能證明貪婪選擇性質）
- 動態規劃（DP）：有重疊子問題 + 最佳子結構 → 把子問題結果記下來（記憶化/表格），避免重算 → 如背包、最長公共子序列。
- 想不到時：先寫暴力解，再找「重複計算」或「可拆解」的結構往上述三類靠。
★ 從題目的「訊號」辨認策略
| 題目裡出現的訊號 | 優先考慮 | 為什麼 |
|---|---|---|
| 「最多／最少／最大／最小」+「有很多種選法」 | 動態規劃 | 最佳化問題；選法之間常共享子問題 |
| 「有幾種方法」 | 動態規劃 | 計數問題幾乎都是 DP |
| 每一步的選擇不會影響之後的選項 | 貪婪 | 但要能證明（見下） |
| 資料可以切成獨立的兩半各自處理 | 分治 | 合併排序、最近點對 |
| 輸入已排序，或答案有單調性（「值越大越容易滿足」） | 二分搜尋（包括對答案二分） | 每步砍掉一半 |
| 「連續子陣列／子字串」+ 某種條件 | 滑動視窗或雙指標 | O(n) 而不是 O(n²) |
| 「列出所有」組合／排列／路徑 | 回溯（DFS + 剪枝） | 答案本身就是指數級，只能靠剪枝加速 |
| 關係、依賴、連通、路徑 | 圖演算法（BFS、DFS、拓撲排序、最短路徑） | 先把問題建模成圖 |
★ 貪婪：一個反例就能推翻
找零問題：硬幣面額 {1, 3, 4}，湊出 6 元，最少幾枚？
- 貪婪（每次拿最大的）：4 → 剩 2 → 1 + 1，共 3 枚。
- 最佳解：3 + 3，共 2 枚。
貪婪在台幣面額 {1, 5, 10, 50} 上是對的，換一組面額就錯了。所以「貪婪看起來很合理」不是證明。
證明貪婪正確的標準方法（交換論證）：假設有一個最佳解和貪婪的選擇不同，證明可以把最佳解中的某個選擇換成貪婪的選擇，而結果不會變差。如果換得過去，貪婪就是對的；換不過去，通常就找到了反例。
實務做法：寫一個暴力解，用小輸入（n ≤ 10）大量比對貪婪解和暴力解。對不上就代表貪婪錯了。
★ 動態規劃的四步設計法
- 定義狀態：
dp[i]代表什麼？要精確到一句話——「前 i 個物品、容量 j 時的最大價值」。狀態定義錯了，後面全錯。 - 寫轉移方程式：
dp[i]怎麼從更小的狀態算出來？通常是「最後一步做了什麼選擇」的所有可能取最佳。 - 確定初始值與計算順序：
dp[0]是什麼？計算dp[i]時，它依賴的狀態已經算好了嗎？ - 複雜度 = 狀態數 × 每個狀態的轉移成本。例如 LCS：狀態 m×n，每個 O(1) → O(mn)。
★ 暴力解 → 最佳解的標準路線
暴力解（列舉所有可能）
↓ 發現大量重複計算？ → 記憶化（DP）
↓ 發現不需要考慮所有可能？ → 剪枝（回溯）或貪婪
↓ 發現有序或單調？ → 二分搜尋
↓ 發現內層迴圈在找東西？ → 換資料結構（map、heap）把內層降到 O(1) 或 O(log n)
第一步永遠是寫出暴力解：它是正確性的基準，也是找出「哪裡在浪費」的起點。
🧪 我實際套用的紀錄
- 2026-07-15：（待填）
⚠️ 注意
- 貪婪不是萬用——很多問題貪婪會得到次佳解，需要 DP。用小例子驗證。
🔗 相關工具
- 工具-時間複雜度分析 —— 挑策略的量尺，判斷換策略後真的降階了還是只是換寫法
- 工具-程式問題解決策略 —— 上位流程，這張是它「辨認問題類型」那一步的專用工具箱