算法设计范式
记忆化
记忆化是这样一个技巧：让一个函数记住它已经算过的结果，于是重复的调用能立刻返回保存好的答案，而不必把活儿重新干一遍。这个词源自 memo——写给自己的备忘条。它就是「自顶向下」穿戴起来的动态规划：你保留自然的递归写法，但第一次算出某个输入的答案时，就把它塞进一个缓存（哈希表或数组），日后每一次对同一个输入的调用都只是一次快速查表。
教科书式的例子是斐波那契。朴素递归 fib(n) = fib(n-1) + fib(n-2) 正确却灾难性：它把同样的值重算了指数多次，代价约为 O(2^n)。加上一个缓存——递归前先查它，返回前先存它——每个 fib(k) 就只算一次。运行时间随之坍缩到 O(n)，因为只有 n 个不同的子问题、每个只解一次；你额外花 O(n) 的内存来存放这些答案。
当一段递归存在重叠子问题、而你又不想把它改写成自底向上的循环时，记忆化最为出彩。它只计算你真正到达的子问题（不像填表法会把整张表填满），当可达状态稀疏时这会是实打实的便宜。代价是缓存占用的内存外加一点查表开销；而且你必须小心地用「一切会影响答案的东西」来作缓存的键——键弄错了，它就会乐呵呵地返回一个过时、错误的结果。
vector<long long> memo; // memo[i] = -1 means "not computed yet"
long long fib(int n) {
if (n < 2) return n;
if (memo[n] != -1) return memo[n]; // cache hit
return memo[n] = fib(n - 1) + fib(n - 2); // compute once, store
}
// init: memo.assign(n + 1, -1);把 O(2^n) 的朴素递归变成 O(n)——每个子问题恰好解一次。
记忆化（自顶向下）与填表法（自底向上）是动态规划的两种标准实现。记忆化不过是给递归加一层缓存；填表法则用迭代把同样的答案重新搭起来。当递归已经写得很清楚、且只用得到部分状态时，就选记忆化。
又称
另见