01先把问题说具体
求爬 n 级楼梯的方法数,每次走 1 或 2 级。递归式相同的子问题为何被计算了很多遍?
02一步步得到方法
先写没有缓存的依赖树
ways(n)=ways(n−1)+ways(n−2),ways(0)=1、ways(1)=1。ways(5) 调用 ways(4) 与 ways(3),而 ways(4) 又调用 ways(3),相同参数的答案被重复求解。
记忆化把完成的 ways(k) 保存起来,下次进入同一状态直接返回。它保留递归表达式的自然结构,却把展开树压缩为每个状态只求一次的依赖图。
缓存键必须包含决定答案的全部信息
若背包结果依赖物品下标和剩余容量,键必须是 (i,c),不能只用 c。若函数读取可变外部数据,即使参数相同,答案也可能变化,旧缓存就失效。
缓存不自动解决环依赖。若 f(a) 在完成前又调用 f(a),缓存里还没有结果,仍会无限递归。必须证明状态严格推进,或采用专门的图算法和迭代不动点方法。
缓存键必须完整描述子问题
如果子问题结果还依赖背包剩余容量,就不能只用物品下标作为缓存键。两个调用键相同就必须意味着返回值相同,否则缓存会把不同问题错误合并。
闭包中的图、价格或其他输入改变后,旧缓存可能失效。缓存适合输入固定的纯子问题;副作用、随机性或依赖当前时间的计算需要额外设计。
03把一个小例子完全算清楚
ways(5),按第一次请求的顺序展开。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 向下展开 | 5→4→3→2→1、0 | 先到基例 |
| 返回并缓存 | ways(2)=2,ways(3)=3 | 重复访问直接取缓存 |
| 继续合并 | ways(4)=5,ways(5)=8 | 每个 k 只真正计算一次 |
窄屏可左右滑动表格,阅读完整计算与理由。
缓存复用的是相同状态的完整答案,不是随意复用看起来相似的局部变量。
04为什么这个方法成立
- 递归基例正确。
- 对更小状态答案正确时,最后一步为 1 或 2 的两类方案互斥且穷尽,递推正确。
- 缓存返回的正是此前同一状态的正确答案,因此只改变执行次数,不改变数学含义。
05把推导翻译成代码
Python · 可独立运行的教学实现
from functools import cache
def count_ways(n):
assert n >= 0
@cache
def ways(k):
if k <= 1:
return 1
return ways(k-1) + ways(k-2)
return ways(n)逐个理解关键决定
@cache- 以函数参数为键存结果,不需要手动判断字典是否存在。
def ways(k)- 缓存放在本次外层调用内部,不会无界保留所有历史任务。
06时间、空间与实现范围
有 n+1 个状态,每个常数次转移,固定宽度算术模型下 O(n) 时间;缓存与调用栈 O(n)。
Python 递归深度有限,n 很大时即使时间线性也可能 RecursionError,应改成自底向上;方案数增长时大整数成本另计。
07改变条件,检查哪里会出错
以缓存替代终止条件
循环依赖或不缩小参数仍会无法结束。
把可变对象直接当缓存键
列表等通常不可哈希;应使用稳定不可变状态,并避免调用后改变其语义。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
为何 ways(0)=1 而不是 0?
需要一点提示
已经没有台阶,还需选择什么?
查看解析与答案
空走法是一种完成方式,使 ways(2)=ways(1)+ways(0)=2。
给函数增加可用步长集合后,缓存键如何变化?
需要一点提示
结果是否还只由 n 决定?
查看解析与答案
若步长集合在每次外部调用中固定,可闭包隔离缓存;若同一缓存跨不同集合复用,则键也要包含集合。
怎样去掉递归栈?
需要一点提示
按依赖先后填表。
查看解析与答案
从 0、1 向上计算到 n;本例只依赖前两项,还能滚动成两个变量。