演算法圖鑑
演算法 · 11 個細項

Dynamic Programming動態規劃

DP 的核心是兩件事：子問題會重複出現、大問題的最佳解由子問題的最佳解組成。從記憶化開始，學會定義狀態、寫轉移式、決定順序，再看背包、序列、網格、區間、位元遮罩與樹上這幾種最常見的狀態設計。

為什麼要學 Dynamic Programming

現實中的應用
拼字檢查與自動校正

「teh」和「the」差多少？編輯距離算的就是最少改幾個字，輸入法、搜尋引擎的「你是不是要找」都靠它。

→ 對應課程：Edit Distance
Git diff 與版本比對

兩份文字哪些行沒變、哪些行新增或刪除，本質是最長共同子序列。

→ 對應課程：LCS
預算與資源分配

廣告預算有限、每個方案有成本和效益，選哪些組合效益最大。這是背包問題，雲端資源配置也是同一題。

→ 對應課程：0/1 Knapsack
為什麼不能只用遞迴

費氏數列直接遞迴會重算同樣的子問題幾百萬次。記住答案，就從指數時間變成線性時間，這就是 DP 的起點。

→ 對應課程：Memoization & Tabulation

細項

11 篇
#演算法難度
01Memoization & Tabulation 記憶化與表格法Fibonacci、Climbing Stairs，自頂向下與自底向上用在：任何有重疊子問題的遞迴，先加快取再說021-D DP 一維 DPHouse Robber、Decode Ways，狀態只跟前幾項有關用在：序列決策、簡單的排程與計數030/1 Knapsack 背包問題每個物品選或不選，二維表與空間壓縮用在：預算分配、投資組合、貨櫃裝載04Unbounded Knapsack 完全背包物品可重複選，Coin Change 的 DP 版用在：找零最少硬幣數、無限供應的採購05LIS 最長遞增子序列O(n²) 的 DP 與 O(n log n) 的耐心排序用在：股價趨勢分析、俄羅斯套娃信封問題06LCS 最長共同子序列二維表，相等就對角線加一用在：diff 工具、DNA 序列比對、抄襲比對07Edit Distance 編輯距離插入、刪除、取代三種操作的最小次數用在：拼字校正、模糊搜尋、語音辨識評分08Grid DP 網格路徑Unique Paths、Min Path Sum，只能往右或往下用在：機器人路徑計數、影像接縫裁切09Interval DP 區間 DPBurst Balloons、矩陣鏈乘，枚舉分割點用在：最佳括號化、多邊形三角剖分10Bitmask DP 位元遮罩 DP用整數的位元表示集合狀態用在：TSP、小規模指派問題11Tree DP 樹上 DP後序走訪，由子樹答案組合父節點答案用在：樹的直徑、最大路徑和、樹上獨立集