iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 30
4
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
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中
0
阿展展展
iT邦好手 1 級 ‧ 2019-12-30 06:14:48

恭喜完賽!!!
燒腦30/images/emoticon/emoticon37.gif

卡卡恩 iT邦新手 4 級 ‧ 2020-01-01 10:26:21 檢舉

哈 真的超級燒腦的~謝謝你!

0
polymath
iT邦新手 5 級 ‧ 2020-05-17 23:30:58

終於做完這一系列了,雖然大部分題目一開始都想不出來,但這種腦力激盪(ㄗˋ ㄋㄩㄝˋ)的感覺真是不錯,雖然一開始進來是為了準備面試,本來想說看到少考的就跳過,後來還是想說想不出來搞懂了也未嘗不好,就默默的看完了...雖然花了很多時間搞懂,功力還是遠遠不夠,不過anyway感謝大大的分享,至少目前沒有看到其他有人整理這麼豐富的dp大集合。

卡卡恩 iT邦新手 4 級 ‧ 2022-10-13 12:01:58 檢舉

謝謝你熱情地一起把這系列題目做完~~~!!!

0
iamlockon
iT邦新手 5 級 ‧ 2021-06-26 22:53:50

感謝大大分享,祝大大一生平安~
最後有個問題想請教,大大有沒有一些突破解題卡關的心得,我卡在一個不上不下的階段很久(至少一年多了),不確定要怎麼辦才能突破.

卡卡恩 iT邦新手 4 級 ‧ 2022-10-13 12:05:25 檢舉

我有個想法提供給您 可以參考看看~ 比較 hardcore 的方法是想破頭都想不出來才去看討論串(的標題!) 通常標題會很爆雷地告訴你這題要用什麼方法做。然後照著那個想法再繼續想下去,如果還是毫無頭緒再點進去看答案~ 比較沒那麼 hardcore 的方法就是把想破頭的時間縮短成五分鐘,而且是紮紮實實的五分鐘~

我要留言

立即登入留言