演算法設計範式
動態規劃
動態規劃是這樣一門手藝：先解出一個問題的更小子問題、並把它們的答案記下來，從而讓任何子問題都不會被解第二次。儘管名頭唬人（這名字在歷史上其實和「電腦程式設計」毫無關係），核心思想卻樸素而有力：當一個問題反反覆覆地撞上同樣的小問題時，就把每個答案寫進一張表裡，下次直接查表，而不是重算。你用一點記憶體，換來時間上的巨大節省。
有兩樣配料能讓一個問題適合用 DP。其一是重疊子問題：樸素遞迴會把同一個子問題解很多遍——想想用遞迴算費氏數時，fib(2) 被一遍又一遍地索要。其二是最優子結構：整體的最優答案由各部分的最優答案搭成，所以一個子問題的答案一旦敲定，就再也不必修改。當兩者都成立時，你就能填一張子問題答案表——要麼自頂向下用記憶化（照樣遞迴，但把每個結果快取起來），要麼自底向上用列表填表法（從最小情形出發，用迴圈逐層往上搭）。
回報往往是從指數時間一躍到多項式時間。費氏數從 O(2^n) 降到 O(n)。0/1 背包、最長公共子序列、編輯距離、帶權圖上的最短路徑，都能用 DP 拿下，時間通常是 O(n·W) 或 O(n·m)——即表的大小乘以每格的工作量。功夫全在於看出正確的子問題定義（即「狀態」）以及把狀態串起來的遞迴關係；這兩樣一旦擺對，程式碼幾乎是自己寫出來的。代價是表佔用的記憶體，不過精巧的 DP 往往只需保留最後一兩列。
long long fib(int n) {
if (n < 2) return n;
vector<long long> dp(n + 1);
dp[0] = 0; dp[1] = 1; // base cases
for (int i = 2; i <= n; ++i)
dp[i] = dp[i - 1] + dp[i - 2]; // optimal substructure
return dp[n]; // O(n) time and space
}時間 O(n)、空間 O(n)——只保留兩個值就能把空間壓到 O(1)。
自頂向下（記憶化遞迴）與自底向上（填表法）是同一套 DP 的兩副面孔。自頂向下更貼近你的思路，且只計算真正用得到的狀態；自底向上免去遞迴開銷，也更便於把記憶體壓縮到最後幾列。無論哪種，遞迴式都是同一個。
又稱
另見