相同子问题不再反复展开
按递推式直接求斐波那契数时，同一个较小下标会出现在许多递归分支中。记忆化把已经得到的结果按下标存下，再次遇到同一子问题时直接复用，避免重新展开整棵重复计算树。
这里的缓存键必须完整描述决定答案的状态。若剩余预算、已用项目或其他约束影响结果，却没有纳入状态，就可能把不同问题误认成同一个。动态规划的正确性首先来自恰当的子问题定义，不是随便给递归函数加一张表。
参考：[1]
自顶向下与自底向上
记忆化通常按实际调用自顶向下计算；列表式方法则按依赖顺序自底向上填表，让所需子答案先于使用它的状态完成。斐波那契数依次用前两项计算下一项，两种方式可以表达相同递推关系。
简单记忆化并不自动消除循环依赖。求图中最短路时，若状态只按当前顶点定义，环可能让递归无休止；加入允许使用的边数等维度，可以把依赖变成逐层推进。状态数量增加与依赖变得可计算之间，需要一起分析。
参考：[1]
数清状态与每个状态的工作
分析时应数出状态总量，再统计每个状态尝试多少候选转移。某种设计可以消除大量重复计算，却仍含指数数量的不同状态；“用了动态规划”不等于问题就必然有多项式解法，也不等于当前状态是最节省的一种。
斐波那契表可压缩为只保存前两项，因为更早的值不再被下一步使用；需要恢复完整解法时则可能还要保存选择信息。这里的线性运算次数与常数个存储数值，采用算术操作模型；整数位数增长时，其位运算与实际存储成本仍应另算。