《圖解演算法：使用 C#》讀書筆記 2

書籍資訊

這一篇不是專講某一題，而是在整理幾種解題時非常常見的套路。當題目一來，很多時候先判斷「這題像哪一類」，會比直接硬寫更有效率。

這篇主要整理了：

分治法的核心精神是把一個大問題拆成幾個相似的小問題，分別解完之後再合併結果。

它通常會經過三步：

這種方法適合子問題彼此相對獨立，而且合併規則清楚的情況。像是合併排序、快速排序，都是很典型的例子。

遞迴就是函式呼叫自己。寫遞迴時最重要的是兩件事：

如果這兩件事沒先想清楚，遞迴通常不是難讀，就是直接失控。

遞迴很適合處理有明顯層次或樹狀結構的問題，例如：

動態規劃處理的是「重複子問題」。如果同一批中間結果會被反覆用到，就可以把它們存下來，避免重算。

它的核心通常是：

和單純遞迴相比，DP 的差異不在於有沒有拆子問題，而在於有沒有系統性地重用答案。

有些問題不一定要用遞迴，改用迴圈一步一步往前推，反而更直接也更好控制。

迭代常見的優點是：

很多遞迴解，其實都可以改寫成迭代解，差別只在於狀態是放在系統堆疊裡，還是你自己手動管理。

回溯可以看成一種有策略的暴力搜尋。先嘗試一條路，如果走不通，就退回上一步改試別條路。

它常出現在：

回溯的關鍵不只是「試」，而是要知道什麼時候應該撤退，以及怎麼避免無效搜尋。

貪心法的做法是每一步都先選當下看起來最好的方案，希望一路累積成全域最佳解。

它的好處是：

但限制也很明顯：

所以貪心法能不能成立，核心不是寫起來順不順，而是你能不能證明這個選擇策略是正確的。

這篇其實很像演算法工具箱的索引。遇到新題目時，可以先這樣想：

這種分類不一定一次就判斷正確，但至少能讓找解法的方向更快收斂。