专题进阶 · 动态规划推荐总顺序 · 第 63 / 148 课

把递归状态作为缓存键,分清重复子问题与环依赖。

先学会这些,再进入本课 DP 思想 递归与调用栈 哈希表
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 动态规划

记忆化搜索Memoization

在递归入口缓存状态结果,自顶向下只计算被访问的状态。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

把递归状态作为缓存键,分清重复子问题与环依赖。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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. 对更小状态答案正确时,最后一步为 1 或 2 的两类方案互斥且穷尽,递推正确。
  3. 缓存返回的正是此前同一状态的正确答案,因此只改变执行次数,不改变数学含义。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

为何 ways(0)=1 而不是 0?

需要一点提示

已经没有台阶,还需选择什么?

查看解析与答案

空走法是一种完成方式,使 ways(2)=ways(1)+ways(0)=2。

练习 2 · 边界与辨析

给函数增加可用步长集合后,缓存键如何变化?

需要一点提示

结果是否还只由 n 决定?

查看解析与答案

若步长集合在每次外部调用中固定,可闭包隔离缓存;若同一缓存跨不同集合复用,则键也要包含集合。

练习 3 · 变式与迁移

怎样去掉递归栈?

需要一点提示

按依赖先后填表。

查看解析与答案

从 0、1 向上计算到 n;本例只依赖前两项,还能滚动成两个变量。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。