演算法洞見：遞推與遞迴

第一章 觀念與實作
1.1 觀念
1.2 實作
準備一棵樹
以遞推程式碼實作遞推觀念
以遞迴程式碼實作遞推觀念
以遞迴程式碼實作遞迴觀念
「好」的遞迴與「壞」的遞迴
以遞推程式碼實作遞迴觀念
思考題

第二章 實作回溯：上古神話中的演算法
2.1 回溯式遞迴的基本原理
範例1
範例2
2.2 神話故事中的演算法
迷宮設計入門
探尋迷宮中的路徑
用遞推（迴圈）程式碼實作回溯
思考題

第三章 動態規劃：動機決定性質
3.1 什麼是動態規劃
3.2 透徹理解動態規劃
遞推版動態規劃
遞迴版動態規劃
陷阱：這不是動態規劃！
貪心也要動腦子
3.3 更上層樓：讓規劃「動態」起來
切年糕
接訂單
聽講座
思考題
3.4 動態規劃哲思

第四章 演算法皇冠上的明珠
4.1 遊樂園：O(n^2) 的簡單排序
選擇排序
泡沫排序
插入排序
4.2 以空間換取時間：合併排序
4.3 看運氣的快速排序
4.4 兩全其美：堆積排序
什麼是「堆積」
建構最大/ 最小堆積
利用「最大堆積」進行原地排序
利用「最小堆積」產生升冪陣列
思考題

第五章 搜尋：來而不往非禮也
5.1 二分搜尋
在已排序的陣列上
在平衡二元搜尋樹上
5.2 線段樹：化繁為簡
建構線段樹
查詢子段和
5.3 字典樹：字母大接龍
遞推版實作
遞迴版實作
5.4 併查集：朋友的朋友是朋友

第六章 圖：包羅萬象
6.1 圖的表達
鄰接表
鄰接矩陣
應對向、權、環的變化
思考題
6.2 圖的巡訪
廣度優先巡訪
深度優先巡訪
遞推版深度優先巡訪
向、權、環對巡訪的影響
6.3 頂點的連通性
有無權重對連通性的影響
有無向對連通性的影響
環對連通性的影響
6.4 強連通性元件
Kosaraju-Sharir 演算法
6.5 圖上的路徑
BFS 式路徑搜尋
DFS 式路徑搜尋
自下而上式路徑搜尋
回溯式路徑搜尋
取得環路
思考題
6.6 最短路徑
Dijkstra 最短路徑演算法
Bellman-Ford 最短路徑演算法
Floyd-Warshall 最短路徑演算法
6.7 最小生成樹
建構有權無向圖
Prim 演算法
Kruskal 演算法
6.8 最大流：超時空移花接木
殘差邊、反向邊、殘差網路、增廣路徑
容量返還
Ford-Fulkerson 演算法實作
6.9 最小割：流量的瓶頸
6.10 拓撲排序
入度圖與出度圖
理解頂點的入度
遞推實作
遞迴實作
思考題

A 後記