算法之禪 : 遞推與遞歸

劉鐵猛

高級軟件工程師，技術作者、譯者、教育者，現就職於亞馬遜（美國）。
曾就職於微軟（美國），著有《深入淺出WPF》一書，銷量數万冊。
精心製作的《C#語言入門詳解》視頻課程點擊量超500萬次，是目前全球排名第一的中文C#教程。
他的多套教學視頻已被微軟收錄為官方認證課程。
他的所有作品風格一致：內容詳實準確、語言風趣幽默、說理深入淺出，被學習者們奉為佳作。

目錄
致謝
一夜春風，萬樹梨花
第OO章開篇緒言
緣起
預備知識
第01章思想與實現
思想
實現
準備一棵樹
用遞推代碼實現遞推思想
用遞歸代碼實現遞推思想
用遞歸代碼實現遞歸思想
“好”的遞歸與“壞”的遞歸
用遞推代碼實現遞歸思想
思考題
第02章回溯：上古神話中的算法
回溯式遞歸的基本原理
示例1
示例2
神話故事中的算法
迷宮設計入門
探尋迷宮中的路徑
用遞推（循環）代碼實現回溯
思考題
第03章動態規劃：動機決定性質
什麼是動態規劃
透徹理解動態規劃
遞推版動態規劃
遞歸版動態規劃
陷阱：這不是動態規劃
貪心也要動腦子
更上層樓：讓規劃“動態”起來
切年糕
接訂單
聽講座
思考題
動態規劃哲思
第04章排序：算法皇冠上的明珠
遊樂園：O（n2）的簡單排序們
選擇排序
冒泡排序
插入排序
以空間換時間：歸併排序
看運氣的快速排序
兩全其美：堆排序
什麼是“堆”
構建大/小根堆
利用“大根堆”進行原地排序
利用“小根堆”生成升序數組
思考題
第05章查找：來而不往非禮也
二分查找
在己排序的數組上
在平衡二叉搜索樹上
線段樹：化繁為簡
構建線段樹
查詢子段和
字典樹：字母大接龍
遞推版實現
遞歸版實現
並查集：朋友的朋友是朋友
第06章圖：包羅萬象
圖的表達
鄰接列表
鄰接矩陣
應對向、權、環的變化
思考題
圖的遍歷
廣度優先遍歷
深度優先遍歷
遞推版深度優先遍歷
向、權、環對遍歷的影響
頂點的連通性
有無權重對連通性的影響
有無向對連通性的影響
環對連通性的影響
強連通性組件
Kosaraju-Sharir算法
圖上的路徑
BFS式路徑搜尋
DFS式路徑搜尋
自底向上式路徑搜尋
回溯式路徑搜尋
獲取環路
思考題
最短路徑
Dijkstra最短路徑算法
Bellman-Ford最短路徑算法
Floyd-Warshall最短路徑算法
最小生成樹
構建有權無向圖
Prim算法
Kruskal算法
最大流：超時空移花接木
餘量邊，反向邊，餘量網絡，增益路徑
容量返還
Ford-Fulkerson算法實現
最小割：流量的瓶頸
拓撲排序
生成入度圖與出度圖
理解頂點的入度
遞推實現
遞歸實現
思考題
後記