iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 30
2
Software Development

動態規劃百題之經典、理論與實作系列 第 30

Day 30: 那些沒有提到的動態規劃和還沒做完的題目。

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

這一陣子挑選的練習題主要以 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 時間啊啊啊啊)終於可以開始練下禮拜的馬拉松了(狀態:狂睡)


上一篇
Day 29: 利用一點點的貪婪演算法提升動態規劃效能!
系列文
動態規劃百題之經典、理論與實作30

尚未有邦友留言

立即登入留言