什麼是動態規劃
把問題分成較小的子問題，將子問題的答案記錄在表中重複利用，以避免重複相同計算的演算法設計方法。用於背包問題、硬幣的最少枚數、最長共同子序列、最短路徑等。
日文名稱: 動的計画法
「動態規劃」出現在1領域的3道練習題中（資料結構與演算法等）。
這個名詞所屬的領域: 資料結構與演算法
概念：重疊的子問題只解一次
若直接以遞迴依 fib(n) = fib(n−1) + fib(n−2) 計算費氏數，相同的值會被一再重新計算，呼叫次數呈指數增加（fib(30) 約269萬次）。動態規劃把求過的子問題答案記錄在表中，之後只需查表。如此 fib(n) 只需與 n 成正比的工作量。可以使用的條件是：大問題的最佳解能由較小子問題的最佳解組成（最佳子結構），以及相同的子問題會多次出現（重疊子問題）。
記憶化與填表的方式
實作方式有兩種：保持遞迴形式、把算過的結果記住的記憶化（由上而下），以及從小的子問題開始依序填表的由下而上方式。例如在0/1背包問題中，以「使用到物品 i 為止、容量 c 以內能得到的最大價值」為表，選擇放入與不放入物品中較大者來填表。物品數為 n、容量為 W 時，工作量為 O(nW)。硬幣最少枚數的問題，也能從0圓到目標金額，依序把各金額的最少枚數填入表中求解。
與貪婪演算法的差異及應用
貪婪演算法只是選擇當下最好的一個選項並往前推進，雖然快，但有些問題無法得到最佳解。以1圓、4圓、6圓的硬幣支付8圓時，貪婪演算法為 6 + 1 + 1 共3枚，動態規劃則能求出 4 + 4 共2枚。動態規劃應用廣泛，例如字串的編輯距離與最長共同子序列（diff 指令）、DNA 序列比對、語音辨識的維特比演算法，以及求所有頂點間最短路徑的 Floyd-Warshall 演算法等。
練習動態規劃的題目
以遞迴將求費氏數的函數 fib(n) 定義為「若 n 在1以下則回傳 n，否則回傳 fib(n−1) + fib(n−2)」。呼叫 fib(5) 時，含第一次呼叫在內，fib 被呼叫幾次？
- A6次
- B9次
- C15次
以1圓、4圓、6圓3種硬幣支付8圓。以從大硬幣開始盡量使用的貪婪演算法決定時的枚數，與最少枚數的關係，下列何者正確？
- A貪婪演算法也能得到最少的2枚
- B貪婪演算法為3枚，無法得到最少的2枚
- C貪婪演算法為3枚，這就是最少枚數
常見問題
動態規劃與分治法有什麼不同？
兩者都把問題分成子問題，但在合併排序這類分治法中，子問題不會重疊，因此不需要記錄答案。動態規劃的不同之處，在於相同子問題多次出現時，會記錄並重複利用答案。
動態規劃的弱點是什麼？
需要與表的大小相應的記憶空間與工作量。背包問題的 O(nW) 與容量 W 的值成正比，W 非常大時就不切實際。可以只記錄需要的部分，或只保留前一列的結果，以減少記憶空間。
解析中的「動態規劃」
若使用把算過的值記在表中的記憶化（動態規劃），只需計算 fib(0)～fib(5) 這6種，呼叫也減為9次（2n − 1）。
以遞迴將求費氏數的函數 fib(n) 定義為「若 n 在1以下則回傳 n，否則回傳 fib(n−1) + fib(n−…以動態規劃從小金額開始依序建立「支付0圓到8圓各金額所需的最少枚數」的表，就一定能求出最少枚數。
以1圓、4圓、6圓3種硬幣支付8圓。以從大硬幣開始盡量使用的貪婪演算法決定時的枚數，與最少枚數的關係，下列何者正確？動態規劃逐一物品更新「容量 c 以內可達到的最大價值」的表，對物品數 n 與容量 W 以 O(nW) 求出最佳值。
從（重量, 價值）為 (2, 3)、(3, 4)、(4, 5)、(5, 6) 的4件物品中選擇，放入容量為8的背包。每…