算法设计范式
动态规划
动态规划是这样一门手艺：先解出一个问题的更小子问题、并把它们的答案记下来，从而让任何子问题都不会被解第二次。尽管名头唬人（这名字在历史上其实和「计算机编程」毫无关系），核心思想却朴素而有力：当一个问题反反复复地撞上同样的小问题时，就把每个答案写进一张表里，下次直接查表，而不是重算。你用一点内存，换来时间上的巨大节省。
有两样配料能让一个问题适合用 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 的两副面孔。自顶向下更贴近你的思路，且只计算真正用得到的状态；自底向上免去递归开销，也更便于把内存压缩到最后几行。无论哪种，递推式都是同一个。
又称
另见