今天是最後一天，很開心能夠努力寫完三十天份量的動態規劃介紹。也很感謝不吝追蹤這個系列的邦友們！當初的規劃大概是這樣的，先花個十天寫寫基本的動態規劃概念，然後中間十天提出各種狀態設計和加速的小技巧，最後十天描述動態規劃在各個領域裡頭的應用。不過很可惜的是後面有點沒力氣了，一些經典的單調序列優化、凹凸函數優化、隱藏式馬可夫模型跟各種近似演算法的應用都來不及介紹哈哈(逃避中)。

這一陣子挑選的練習題主要以 Leetcode 為主。而且是使用 Python 來撰寫，而非大家傳統程式設計解題活動方面偏好的 C++、Java 甚至是 Javascript。使用 Python 來寫主要是因為我覺得 Python 在某些語句上比較能夠傳達語意，寫起來沒有 C++ 那麼瑣碎。不過當然也有不太方便的地方就是了。程式碼或解題思路寫得不夠清晰，這部份還請各位邦友提點，我會加以改進的。

最後一天，在這邊補上關於動態規劃的一些性質和觀念，這部份還滿教科書的，我還是比較喜歡使用頭幾天的撰文方式，雖然寫起來很模糊，但是能透過實際舉例來感受動態規劃帶來的好處。

什麼時候適合使用動態規劃？

一道題目如果能夠使用動態規劃，則它的問題結構通常會滿足以下兩個條件：

1. 最優子結構（Optimal Substructure）：如果一個問題的解，拿去對應到的子問題也是最佳的，那我們就說這個問題有最優子結構特性。
2. 子問題重複次數高（Overlapping Subproblems）：在展開遞迴關係的時候，如果重複地化簡到需要同一個子問題的答案，那麼這個問題便有子問題重複次數高的特性。

簡短回顧一下XD

觀念篇

• 遞迴關係→動態規劃：Day 1
• 實作方式：填表方法(Day 2)、遞迴方法(Day 9)
• 關於狀態和轉移：狀態轉移的推與拉(Day 6、Day 16)、動態規劃的維度(Day 8)

經典題目篇

• 費氏數列：Day 1、Day 3
• 找錢問題：Day 1
• 組合數計算：Day 2
• 背包問題：Day 11
• 子矩陣相關問題：Day 5
• 最長共同部分子序列 LCS 與相關延伸：Day 4、Day 6、Day 7、Day 21
• 最長嚴格遞增子序列 LIS 與相關延伸：Day 17、Day 18
• 區間型動態規劃：Day 3、Day 19
• 樹型動態規劃：Day 24
• 指數型動態規劃：Day 14、Day 15、Day 16、Day 28

經典應用篇

• 工作排程相關：Day 10
• 最短路徑問題：Day 22
• 字串匹配相關：Day 23
• 計算幾何相關：Day 25
• 賽局理論相關：Day 26
• 數學相關：Day 20、Day 26、Day 27

加速技巧篇

• Day 9、Day 10、Day 13、Day 29

最後偷偷提一下，動態規劃除了在資訊科學這個領域以外，最大的應用其實是在作業研究（Operations Research，或稱運籌學）主要是研究各種資源配置，用來最佳化某個目標的方法。而更深更廣版的動態規劃在這裡便有著不可或缺的地位。在我們學校中，作業研究好像是歸類在工業工程學系底下的一個重要領域。

耶～終於達成了持續交付三十天了...嗎？（需要更多的 CD 時間啊啊啊啊）終於可以開始練下禮拜的馬拉松了（狀態：狂睡）