鐵人檔案
嗨大家好，我想要利用這個機會幫未來的自己蒐集並整理一些有趣的動態規劃題目，並且試著提出一些自己的心得～
動態規劃是演算法解題中一種常見的解題手段。說穿了，動態規劃就是分而治之法(Divide and Conquer) 搭配紀錄曾經算過的子問題(Memoization) 的一種技巧。至於什麼樣的題目能夠用動態規劃來解，要如何看出一道題目能否使用動態規劃，這時候就要靠大量的例子來自我鍛鍊了。
動態規劃的應用相當廣泛，在生物資訊和組合最佳化的範疇尤其深刻，舉凡路線規劃、空間裝填、序列匹配等都可以看得到動態規劃的影子。如果大家對於我分享的題目有興趣的話，也歡迎補充資料或一起討論！
動態規劃的英文叫做 Dynamic Programming，也就是大家俗稱的低批(DP)，不是打棒球的那個雙殺、不是狄利克雷過程、不是設計模式、也不是指神奇寶貝...
解決不了人的話還是乖乖解決問題吧！填表方法是實作動態規劃演算法的一種方案，而有趣的是，大部分的動態規劃問題也都可以用填表方法來解決。只要找出正確的填表順序即可！...
動態規劃到底可以拿來做什麼呢？根據前兩天我們使用動態規劃解決的問題們，可以歸納出兩種題型：最佳化問題和計數問題。最佳化問題通常要在許多可行解裡面找出一個「最好的...
最長共同部分子序列（Longest Common Subsequence，LCS）是動態規劃入門第一個經典應用。這個問題最早起源於對 DNA 序列的比對問題：如...
二維陣列有很多用途，如果每一個格子的值是 0 或 1 的話，我們稱之為 0-1 矩陣。0-1 矩陣可以表達很多東西，比方說它可以是一個黑白影像、或者是一個運算用...
經過了前五天大量動態規劃的洗滌之後，大家有沒有覺得對填表更加熟悉了呢？在解決動態規劃的問題時，最重要的是定義一個適當的表格（也就是確定問題與子問題的格式）然後，...
今天來多刷點題目好了，明天來講更多經典題！有題能刷直須刷，莫待無題空寫扣。這些內容應該都是前幾天提過的，所以就當作刷習題的感覺來做吧。 Example 12:...
動態規劃的維度 我們可以透過表格的維度、以及轉移所需要考慮的時間，將動態規劃的演算法簡單作一些分類。比方說解決 LCS 的演算法，它是個二維表格、常數時間轉移，...
有的時候，狀態不容易使用表格來表示。又或者，不見得每一個格子都被原本要解的問題依賴。這個時候，就是該使用 Top-Down （遞迴＋記憶化搜索）解法了！記憶化搜...
從今天開始，我們會對「如何定義狀態」這件事情加以琢磨：畢竟不是所有的狀態都可以很直接地從「字串前綴」、「陣列索引」、「數列第 n 項」直接定義出來的。今天來說說...
