鐵人檔案
嗨大家好，我想要利用這個機會幫未來的自己蒐集並整理一些有趣的動態規劃題目，並且試著提出一些自己的心得～
動態規劃是演算法解題中一種常見的解題手段。說穿了，動態規劃就是分而治之法(Divide and Conquer) 搭配紀錄曾經算過的子問題(Memoization) 的一種技巧。至於什麼樣的題目能夠用動態規劃來解，要如何看出一道題目能否使用動態規劃，這時候就要靠大量的例子來自我鍛鍊了。
動態規劃的應用相當廣泛，在生物資訊和組合最佳化的範疇尤其深刻，舉凡路線規劃、空間裝填、序列匹配等都可以看得到動態規劃的影子。如果大家對於我分享的題目有興趣的話，也歡迎補充資料或一起討論！
我們在定義狀態的時候，可以把目前資料的數值當作狀態的其中一個維度。在建立維度的時候，必須要小心數字的範圍，否則可能會造成無窮遞迴、或者是狀態總數過於龐大。其實這...
今天來講講常見的小品序列問題——如果變成了環狀該怎麼辦。大致的想法就是想辦把找到突破口，然後把它拆成數個小題目，每一個小題目都是一般的直線序列問題。 Exerc...
今天來看兩個有趣的題目吧！ Exercise 23: Leetcode 174 - Dungeon Game 題目連結 https://leetcode.com...
在電腦科學的計算理論分支裡面，當今最值得關注的問題莫屬 P 等不等於 NP 的這個問題了。理論學家喜歡把問題歸類：能在多項式時間內解出來的題目被定義成一類 (P...
今天來繼續討論各種有趣的 NP 完備問題吧～ 漢米爾頓路徑問題 (Hamiltonian Path) 給你一個無向、無權重的圖。請問這個圖是否存在一個經過所有點...
今天要討論的是集合覆蓋問題～概念其實跟昨天的旅行售貨員問題很相似喔！ 集合覆蓋問題 (Set Cover) 有 N 個元素以及 M 個子集合，請你找出最少的子集...
今天來聊聊最長嚴格遞增子序列 (Longest Increasing Subsequence, LIS) 吧！ 最長嚴格遞增子序列 (Longest Incre...
今天來看看另外幾個把數值放進狀態、並且帶有 LIS 色彩的動態規劃吧！ Exercise 30: Leetcode 403 - Frog Jump 題目連結 h...
今天來介紹由內而外類型的動態規劃。基本上迴文字串、最佳二元搜尋樹類型的動態規劃就已經算是由內而外了！但有一些這類型的題目想起來還是覺得很精妙的。 Exercis...
是的，今天仍是動態規劃系列。今天來討論哩扣上面跟整除有關的動態規劃問題吧～ Exercise 35: Leetcode 650 - 2 Keys Keyboar...
