iT邦幫忙

鐵人檔案

第 11 屆 iThome 鐵人賽
回列表
Software Development

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

嗨大家好,我想要利用這個機會幫未來的自己蒐集並整理一些有趣的動態規劃題目,並且試著提出一些自己的心得~

動態規劃是演算法解題中一種常見的解題手段。說穿了,動態規劃就是分而治之法(Divide and Conquer) 搭配紀錄曾經算過的子問題(Memoization) 的一種技巧。至於什麼樣的題目能夠用動態規劃來解,要如何看出一道題目能否使用動態規劃,這時候就要靠大量的例子來自我鍛鍊了。

動態規劃的應用相當廣泛,在生物資訊和組合最佳化的範疇尤其深刻,舉凡路線規劃、空間裝填、序列匹配等都可以看得到動態規劃的影子。如果大家對於我分享的題目有興趣的話,也歡迎補充資料或一起討論!

鐵人鍊成 | 共 30 篇文章 | 75 人訂閱 訂閱系列文 RSS系列文
DAY 11

Day 11: 把數字和數量什麼的通通定義到狀態裡面吧!

我們在定義狀態的時候,可以把目前資料的數值當作狀態的其中一個維度。在建立維度的時候,必須要小心數字的範圍,否則可能會造成無窮遞迴、或者是狀態總數過於龐大。其實這...

2019-09-25 ‧ 由 卡卡恩 分享
DAY 12

Day 12: 環狀動態規劃總是比較棘手但也還是能搞定!

今天來講講常見的小品序列問題——如果變成了環狀該怎麼辦。大致的想法就是想辦把找到突破口,然後把它拆成數個小題目,每一個小題目都是一般的直線序列問題。 Exerc...

2019-09-26 ‧ 由 卡卡恩 分享
DAY 13

Day 13: 找出正確的DP方向可以節省一個二分搜尋!

今天來看兩個有趣的題目吧! Exercise 23: Leetcode 174 - Dungeon Game 題目連結 https://leetcode.com...

2019-09-27 ‧ 由 卡卡恩 分享
DAY 14

Day 14: 動態規劃可以解決一些著名的NP完備問題! Part 1

在電腦科學的計算理論分支裡面,當今最值得關注的問題莫屬 P 等不等於 NP 的這個問題了。理論學家喜歡把問題歸類:能在多項式時間內解出來的題目被定義成一類 (P...

2019-09-28 ‧ 由 卡卡恩 分享
DAY 15

Day 15: 動態規劃可以解決一些著名的NP完備問題! Part 2

今天來繼續討論各種有趣的 NP 完備問題吧~ 漢米爾頓路徑問題 (Hamiltonian Path) 給你一個無向、無權重的圖。請問這個圖是否存在一個經過所有點...

2019-09-29 ‧ 由 卡卡恩 分享
DAY 16

Day 16: 動態規劃可以解決一些著名的NP完備問題! Part 3

今天要討論的是集合覆蓋問題~概念其實跟昨天的旅行售貨員問題很相似喔! 集合覆蓋問題 (Set Cover) 有 N 個元素以及 M 個子集合,請你找出最少的子集...

2019-09-30 ‧ 由 卡卡恩 分享
DAY 17

Day 17: 最長嚴格遞增子序列也是動態規劃一大經典!

今天來聊聊最長嚴格遞增子序列 (Longest Increasing Subsequence, LIS) 吧! 最長嚴格遞增子序列 (Longest Incre...

2019-10-01 ‧ 由 卡卡恩 分享
DAY 18

Day 18: 不管是蛙跳能力或是汽駕速度塞狀態就對了!

今天來看看另外幾個把數值放進狀態、並且帶有 LIS 色彩的動態規劃吧! Exercise 30: Leetcode 403 - Frog Jump 題目連結 h...

2019-10-02 ‧ 由 卡卡恩 分享
DAY 19

Day 19: 從內而外更新的動態規劃總是令人讚嘆連連!

今天來介紹由內而外類型的動態規劃。基本上迴文字串、最佳二元搜尋樹類型的動態規劃就已經算是由內而外了!但有一些這類型的題目想起來還是覺得很精妙的。 Exercis...

2019-10-03 ‧ 由 卡卡恩 分享
DAY 20

Day 20: 今天沒什麼論數只好重新檢視數論的問題吧!

是的,今天仍是動態規劃系列。今天來討論哩扣上面跟整除有關的動態規劃問題吧~ Exercise 35: Leetcode 650 - 2 Keys Keyboar...

2019-10-04 ‧ 由 卡卡恩 分享