PYTHON LESSON 090
给递归装上备忘录
看透暴力递归的重复计算，掌握“备忘录”与“递推”两种消除重复的办法，理解二者本质相同。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- if n not in memo: 算过就不再重算
- memo[n] = 递归结果 当场记账
- f[i] = f[i-1] + f[i-2] + f[i-3] 三阶递推
01 · 核心概念
记忆化搜索到动态规划的进化
记忆化搜索到动态规划的进化：每次可跨 1~3 级，爬法数满足 f(n)=f(n-1)+f(n-2)+f(n-3)。直接翻译成递归，每个 f(n) 都会再带出三个调用，像细胞分裂一样膨胀：算 15 级台阶要 3313 次调用，其中 f(5) 这样的小答案被重算了几十遍。
GESP Python 6 级 · 简单动态规划GESP Python 6 级 · 深度优先搜索 DFSlambda 只能包含一个表达式，适合短小的排序键，不适合塞入复杂业务逻辑。
02 · 语法与规则
先记住这 3 条，再开始写程序
if n not in memo: 算过就不再重算先准确读出这条写法的结构与作用。
memo[n] = 递归结果 当场记账换一组最小数据，手工推演一次结果。
f[i] = f[i-1] + f[i-2] + f[i-3] 三阶递推再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 台阶计数器进化史：暴力递归 → 记忆化搜索 → 递推（动态规划）
n = 15 # 每次可以跨 1、2 或 3 级台阶
# 第一代：暴力递归，同一个答案被反复重算
calls = 0
def climb_slow(n):
global calls
calls = calls + 1
if n <= 2:
return n
if n == 3:
return 4
return climb_slow(n - 1) + climb_slow(n - 2) + climb_slow(n - 3)
ans1 = climb_slow(n)
print("暴力递归：", n, "级台阶有", ans1, "种爬法，函数被调用了", calls, "次")
# 第二代：记忆化搜索，算过的答案存进字典
memo = {}
calls2 = 0
def climb_memo(n):
global calls2
calls2 = calls2 + 1
if n <= 2:
return n
if n == 3:
return 4
if n not in memo:
memo[n] = climb_memo(n - 1) + climb_memo(n - 2) + climb_memo(n - 3)
return memo[n]
ans2 = climb_memo(n)
print("记忆化搜索：", ans2, "种爬法，只调用了", calls2, "次")
# 第三代：递推（动态规划），从地基开始一层层往上盖
f = [0] * (n + 1)
f[1] = 1
f[2] = 2
f[3] = 4
for i in range(4, n + 1):
f[i] = f[i - 1] + f[i - 2] + f[i - 3]
print("递推（动态规划）：", f[n], "种爬法，循环只跑了", n - 3, "圈")暴力递归： 15 级台阶有 5768 种爬法，函数被调用了 3313 次 记忆化搜索： 5768 种爬法，只调用了 37 次 递推（动态规划）： 5768 种爬法，循环只跑了 12 圈
三代程序答案完全相同，差别只在“重复算了多少次”——这就是动态规划存在的意义。
04 · 逐步理解
每一步只解决一个问题
- 01
暴力递归贵在哪
每次可跨 1~3 级，爬法数满足 f(n)=f(n-1)+f(n-2)+f(n-3)。直接翻译成递归，每个 f(n) 都会再带出三个调用，像细胞分裂一样膨胀：算 15 级台阶要 3313 次调用，其中 f(5) 这样的小答案被重算了几十遍。
return climb_slow(n - 1) + climb_slow(n - 2) + climb_slow(n - 3) - 02
重复子问题是病根
递归树里同一个 n 出现很多次，而它的答案其实永远不变。“算过的题不算第二次”——这就是记忆化搜索的全部思想，只需要一本字典当备忘录。
memo = {} - 03
查账再算，算完记账
进函数先看 memo 里有没有 n：有，直接返回旧答案；没有，才递归求解，并在返回前把结果写进 memo。只加两行，调用次数从 3313 骤降到 37，效果立竿见影。
if n not in memo: memo[n] = climb_memo(n - 1) + climb_memo(n - 2) + climb_memo(n - 3) return memo[n] - 04
递推：换个方向盖楼
记忆化是“从楼顶往下问，缺什么补什么”；递推是“从地基往上盖”：先填 f[1]、f[2]、f[3]，再按顺序一路算到 f[n]。两者状态、转移一模一样，只是一个自顶向下、一个自底向上。
f[1] = 1 f[2] = 2 f[3] = 4 for i in range(4, n + 1): f[i] = f[i - 1] + f[i - 2] + f[i - 3] - 05
什么时候必须用递推
n 很大时递归会撞深度上限，函数调用本身也有开销；递推纯循环没有这些风险。考级题目把 n 给得很大（还要求对 10^9+7 取模），就是在暗示：请用递推。
- 06
三板斧再默写一遍
状态：f[i] 表示“爬 i 级台阶的爬法数”；转移：f[i]=f[i-1]+f[i-2]+f[i-3]；顺序：从 4 算到 n，初始值 f[1]、f[2]、f[3] 当地基。配套题库题要求取模，记得每步加法之后 % (10**9 + 7)。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，对比三代程序的调用与循环次数
- 2把 n 改成 20，看暴力递归慢了多少
- 3手算 f[4] 到 f[6]，和程序核对
- 4说出备忘录和递推数组的共同作用
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
程序组织函数、参数、返回值与作用域用明确的输入、输出和职责拆分程序，理解参数绑定、作用域、递归与可变对象。＋
正式定义
函数把一段可复用行为绑定到名字。调用时实参按规则绑定到形参，函数执行后用 return 交回结果；没有显式 return 时返回 None。名字解析遵循局部、闭包、全局、内置的 LEGB 顺序。
必须掌握
- 位置参数先于关键字参数；默认值在 def 执行时创建一次，不应直接使用可变容器作默认值。
- return 立即结束当前函数；return a, b 实际返回一个元组。
- 函数内赋值默认创建局部变量；global 声明模块级名字，nonlocal 声明最近外层函数名字。
- 传参传递的是对象引用；函数是否影响调用方取决于对象是否可变以及函数是否原地修改。
- 递归必须有可到达的终止条件，并要考虑调用深度、重复子问题和栈空间。
- 纯函数更容易测试；把输入输出、计算逻辑和全局状态分开能显著减少错误。
常见误区
- 可变默认参数在多次调用间共享
- 忘记 return 导致得到 None
- 局部变量遮蔽全局同名变量
- 递归没有缩小问题规模
适用边界
- lambda 只能包含一个表达式，适合短小的排序键，不适合塞入复杂业务逻辑。
- 装饰器、生成器和闭包属于函数模型的进阶应用，应在基本参数与作用域稳定后学习。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
算法方法动态规划、贪心与分治根据子问题关系选择 DP、贪心或分治，并能说明状态、转移、顺序和正确性。＋
正式定义
动态规划保存重叠子问题的结果，通常依赖最优子结构；贪心每步做局部选择，必须证明它能导向全局最优；分治把问题拆成相互独立的同类子问题，递归求解后合并。
必须掌握
- DP 四要素是状态含义、初始值、转移方程和计算顺序，最后还要明确答案位于哪里。
- 记忆化搜索是自顶向下按需计算，表格 DP 是自底向上按依赖顺序计算。
- 滚动数组只能压缩已经不会再使用的维度，更新方向必须避免覆盖仍需读取的旧状态。
- 贪心要有交换论证、领先法或结构性质证明，样例上成功不是证明。
- 归并排序把序列分半、分别排序再线性合并，时间 O(n log n)、额外空间 O(n)。
- LIS、LCS、0-1 背包和区间 DP 的状态定义不同，不能只替换模板变量名。
常见误区
- 状态定义不含必要信息
- 转移顺序读取到本轮新值
- 没有证明就使用贪心
- 把连续子数组和子序列混为一谈
适用边界
- 同一问题可能有多种复杂度方案，课程会同时保留清晰基线与优化版。
- DP 不是枚举所有状态就结束；状态数与每次转移成本共同决定复杂度。
完成检查