02.6.1.3 记忆化与递归转迭代
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归 / 02.6.1 递归与回溯框架
02.6.1.3-001 怎么识别重叠子问题?
一句话结论
递归展开后同一状态被多次计算,即存在重叠子问题;表现为递归树出现重复子树,朴素递归时间随重复次数指数膨胀,可用记忆化或 DP 消除。
概念解释
- 状态:决定后续计算的输入参数组合。
- 重复子树:相同状态再次出现。
原理流程
- 画递归树。
- 标记重复出现的节点。
- 重复越多,记忆化收益越大。
代码 / 图示
fib(4)
├ fib(3)
│ ├ fib(2) ← 重复
│ └ fib(1)
└ fib(2) ← 重复
常见误区
- 误区:递归调用次数多就是重叠子问题;正解:必须是相同状态重复求解,不同状态不算。
- 误区:树遍历有重叠子问题;正解:每个节点只访问一次,无重复。
追问
- Q:重叠子问题是 DP 前提吗? A:是,配合最优子结构才可 DP。
- Q:怎么快速判断? A:看递归参数是否反复取到相同组合。
02.6.1.3-002 记忆化搜索怎么实现?
一句话结论
用 memo 数组或哈希表缓存每个状态的结果;进入递归先查缓存,命中直接返回;未命中则计算并存入缓存后返回;状态键由影响结果的参数组成。
概念解释
- memo:状态到结果的映射。
- 命中:直接复用。
- 未命中:计算并回填。
原理流程
- 进入函数先查 memo。
- 未命中执行递归计算。
- 结果写入 memo 再返回。
代码 / 示例
int[] memo;
int dfs(int i) {
if (memo[i] != -1) return memo[i];
int res = ...;
memo[i] = res;
return res;
}
常见误区
- 误区:缓存初始值与合法结果冲突;正解:用 -1、null 或单独标记位表示未计算。
- 误区:缓存键漏掉状态维度;正解:所有影响结果的参数都要进键。
追问
- Q:记忆化和自底向上 DP 结果一致吗? A:一致,只是计算方向相反。
- Q:缓存存最优值还是全部解? A:按题意,计数/最值存标量,枚举路径一般不缓存。
02.6.1.3-003 自顶向下与自底向上怎么选?
一句话结论
自顶向下是递归 + memo,按自然思路分解,易写出但有栈深开销;自底向上是 DP 数组按顺序递推,无递归栈、易空间优化;状态转移清晰后通常改自底向上。
概念解释
- 自顶向下:从原问题递归到基准。
- 自底向上:从基准递推到原问题。
原理流程
- 先写递归思路。
- 加 memo 验证状态。
- 再按依赖顺序填表。
代码 / 示例
斐波那契:递归 memo 自上而下;数组 f[0..n] 自下而上
常见误区
- 误区:自底向上必须先想透递归;正解:可直接按状态定义填表。
- 误区:两种方式遍历顺序相同;正解:方向相反,依赖状态先算。
追问
- Q:哪种更省栈? A:自底向上无递归栈。
- Q:哪种更容易剪枝? A:自顶向下可在不命中分支提前返回。
02.6.1.3-004 记忆化和 DP 是什么关系?
一句话结论
记忆化搜索是自顶向下的 DP:状态定义、转移方程与自底向上 DP 完全相同,区别只是计算方向;memo 数组对应 DP 表,缓存命中对应查表。
概念解释
- 状态:memo 键 / DP 下标。
- 转移:递归关系 / 递推方程。
- 基准:memo 基准值 / DP 初始化。
原理流程
- 确定状态与转移。
- 递归版加缓存。
- 等价改写为填表版。
代码 / 示例
memo[i] = f(memo[...]) ↔ dp[i] = f(dp[...])
常见误区
- 误区:记忆化不算 DP;正解:它是 DP 的递归实现形式。
- 误区:记忆化缓存的是路径;正解:通常缓存状态值,路径另存。
追问
- Q:什么时候保留递归 memo 写法? A:状态稀疏、只访问部分状态时。
- Q:DP 表满填但状态很少怎么办? A:记忆化更省未访问状态。
02.6.1.3-005 缓存状态怎么设计?
一句话结论
缓存键必须包含所有影响后续结果的参数:下标、剩余容量、剩余和、位置状态等;值存该状态下的最优值/计数/可行性;维度多时用多维数组或编码成整数/字符串键。
概念解释
- 状态维度:决定结果的全部输入。
- 键编码:多维压成数组下标或整数。
原理流程
- 列出影响结果的参数。
- 确定值域选数组或哈希。
- 定义缓存值含义。
代码 / 示例
// 二维状态:(i, j)
int[][] memo = new int[n][m];
// 多维可编码:key = i * m + j
常见误区
- 误区:把不影响结果的参数也放进键;正解:只保留状态维度,减少缓存规模。
- 误区:缓存值含义前后不一致;正解:明确存最值、计数还是布尔。
追问
- Q:状态维度太多怎么办? A:评估状态压缩或换题型,n 过大时 memo 不可行。
- Q:哈希键怎么构造? A:拼接维度或编码整数,保证唯一映射。
02.6.1.3-006 记忆化数组怎么初始化与判命中?
一句话结论
用不可能作为合法结果的值标记未计算(如 -1、-INF),进入先判断是否已算;合法结果可能为负时,需用独立布尔数组或 null 包装区分“未计算”与“结果为负”。
概念解释
- 哨兵值:表示未缓存。
- 冲突:合法结果等于哨兵。
原理流程
- 选不冲突的哨兵。
- 初始化全部为哨兵。
- 命中判断后再取值。
代码 / 示例
Arrays.fill(memo, -1);
if (memo[i] != -1) return memo[i];
// 结果可能为负:用 Boolean[] 或 Integer[] null 判断
常见误区
- 误区:结果可为负还拿 -1 当哨兵;正解:换 null 或独立标记数组。
- 误区:缓存未命中就覆盖基准值;正解:基准也应写入缓存。
追问
- Q:对象结果用什么标记未算? A:null。
- Q:初始化代价多大? A:与状态空间同阶。
02.6.1.3-007 什么场景记忆化不能用?
一句话结论
当结果依赖完整历史路径(已选集合、路径顺序、访问过的具体元素),而历史无法被有限状态维度表达时,记忆化会把不同历史误判为同一状态;此时只能回溯枚举。
概念解释
- 路径依赖:历史选择影响后续。
- 状态不可约:历史无法压缩成少量维度。
原理流程
- 检查后续选择是否只依赖当前状态。
- 若依赖已选集合/顺序,缓存失真。
- 保留回溯枚举。
代码 / 示例
排列枚举:历史顺序不同即不同解,memo 无法合并
常见误区
- 误区:把路径本身当缓存键;正解:路径长度随规模增长,缓存失去意义。
- 误区:认为加了 memo 就一定提速;正解:状态不可缓存时反而增加开销。
追问
- Q:子集和计数能记忆化吗? A:状态 (下标, 剩余和) 可缓存,与具体选法无关时可以。
- Q:棋盘摆放能缓存吗? A:占用布局是状态,规模小可掩码缓存。
02.6.1.3-008 递归转迭代:显式栈模拟的基本思路?
一句话结论
把递归帧的参数、局部变量、返回位置压入显式栈;弹出时按状态位判断是首次进入还是子节点已返回,首次进入则压回本帧并压子帧,返回阶段做合并。
概念解释
- 帧对象:参数 + 局部 + 状态位。
- 状态位:待进入 / 子节点已完成。
原理流程
- 构造根帧压栈。
- 弹出帧,按状态位处理。
- 需要子问题则压回本帧再压子帧。
代码 / 示例
Deque<Frame> st = new ArrayDeque<>();
st.push(new Frame(root, 0));
while (!st.isEmpty()) {
Frame f = st.pop();
if (f.state == 0) { /* 压回并压子节点 */ }
else { /* 合并子结果 */ }
}
常见误区
- 误区:只压参数不压状态位;正解:后序合并必须记录执行到哪一步。
- 误区:子帧压栈顺序与递归一致;正解:栈 LIFO,压入顺序要反转才能保持原访问序。
追问
- Q:为什么需要状态位? A:区分进入帧与子帧返回后的合并阶段。
- Q:纯前序递归好转吗? A:好转,无需返回阶段合并。
02.6.1.3-009 迭代栈里要保存哪些帧信息?
一句话结论
保存递归函数的入参、本层局部变量、当前执行位置(返回点);合并阶段需要的子结果也要随帧保留;对照原递归函数的参数表与局部变量逐项列出。
概念解释
- 入参:递归参数。
- 局部:本层中间值。
- 返回点:执行到第几个子调用。
原理流程
- 读原递归函数参数与局部。
- 映射为帧字段。
- 合并阶段从帧内取子结果。
代码 / 示例
帧:{入参 i, 左子结果, 右子结果, 状态位}
常见误区
- 误区:遗漏本层局部变量;正解:合并时用到的中间值必须随帧保存。
- 误区:把子结果存在全局变量;正解:多分支下应挂在各自帧上。
追问
- Q:帧对象怎么定义? A:内部类含参数字段与状态枚举。
- Q:迭代栈空间多少? A:与递归栈深同阶 O(h)。
02.6.1.3-010 后序类问题怎么转迭代栈?
一句话结论
后序需要左右子树结果返回后再处理当前节点;迭代时先压当前帧标记“待合并”,再压右子帧、左子帧;子帧全部弹出后,当前帧进入合并阶段读取子结果。
概念解释
- 后序:左右根。
- 栈序:先压右后压左,保证左先出。
原理流程
- 压根帧待合并。
- 弹出待合并帧时压回并压子帧。
- 子帧完成后回到本帧合并。
代码 / 示例
push(root, 待合并)
pop → push(self, 合并) → push(right) → push(left)
常见误区
- 误区:先压左后压右;正解:栈 LIFO,要左先出须先压右。
- 误区:合并阶段重复访问子节点;正解:子结果已存帧内,直接读取。
追问
- Q:二叉树后序迭代常用什么标记? A:访问标记或记录上次访问节点。
- Q:树形 DP 能这样转吗? A:能,帧内保存左右子树返回值。
02.6.1.3-011 回溯怎么迭代化?
一句话结论
显式栈保存当前路径与候选下标;每帧记录已尝试到第几个选择,弹出时撤销本层选择并推进下一个候选;等价于把递归调用栈换成手动栈,路径仍需做选择/撤销。
概念解释
- 栈帧:路径 + 当前候选位置。
- 撤销:出栈时移除本层选择。
原理流程
- 压根帧。
- 取帧候选,合法则加入路径压子帧。
- 帧耗尽出栈并撤销。
代码 / 示例
栈元素:{路径, start}
候选耗尽 → 路径弹出末位 → 父帧推进候选
常见误区
- 误区:迭代回溯不需要撤销;正解:路径复用,出栈仍要恢复。
- 误区:候选指针忘记推进;正解:每帧记录尝试到的下标,避免死循环。
追问
- Q:迭代回溯可读性如何? A:较差,工程上递归优先,栈深受限再迭代。
- Q:收集结果时机变吗? A:不变,到达结束条件即拷贝路径。
02.6.1.3-012 递归转迭代的代价怎么对比?
一句话结论
迭代省去调用栈但需手动管理帧与状态位,代码复杂度上升;空间上迭代用显式栈与递归栈同阶,部分场景可滚动变量压到 O(1);选择取决于栈深约束与可读性要求。
概念解释
- 调用开销:递归帧压弹。
- 手动管理:帧结构与状态机。
- 空间:显式栈 vs 递归栈。
原理流程
- 评估递归深度是否越界。
- 估算迭代帧字段数量。
- 在可读性与约束间取舍。
代码 / 示例
斐波那契:递归 O(n) 栈 → 滚动变量 O(1) 空间
常见误区
- 误区:迭代一定省空间;正解:显式栈仍占 O(h),只有可滚动状态才能压空间。
- 误区:转换后代码一定更短;正解:状态机写法通常更长。
追问
- Q:什么情况必须转迭代? A:递归深度可能溢出的长链/深层网格。
- Q:迭代版怎么验证等价? A:小用例对比两版输出。
02.6.1.3-013 函数式递归与命令式迭代怎么对照?
一句话结论
函数式递归靠表达式组合结果,状态不可变;命令式迭代靠循环变量原地更新;对照时把递归的“子结果合并”翻译成循环里对累积变量的更新。
概念解释
- 函数式:纯表达式、无共享可变状态。
- 命令式:循环修改变量。
原理流程
- 识别递归的累积量。
- 映射为循环变量初值与更新式。
- 基准映射为循环退出条件。
代码 / 示例
// 递归:sum = a[i] + sum(i+1)
// 迭代:acc = 0; 从后往前 acc += a[i]
常见误区
- 误区:递归的返回值直接对应一个循环变量;正解:多分支合并可能需要多个累积量。
- 误区:方向照搬;正解:自顶向下递归常对应反向迭代。
追问
- Q:尾递归最容易翻译成什么? A:循环加累积参数。
- Q:不可变优势是什么? A:无共享状态副作用,便于推理。
02.6.1.3-014 栈溢出风险下怎么改造?
一句话结论
先估算最坏递归深度;接近上限时优先改迭代(显式栈或滚动变量),或改分治降低树高;不要依赖运行环境尾递归优化,也不应只靠调大栈容量掩盖问题。
概念解释
- 最坏深度:最长调用链。
- 改造方向:迭代化、扁平化、平衡化。
原理流程
- 评估深度与栈容量。
- 可滚动则改循环。
- 树形则显式栈或平衡划分。
代码 / 示例
长链表递归反转 → 三指针迭代
深层网格 DFS → 显式栈 DFS
常见误区
- 误区:调大线程栈就能上线;正解:只是推迟溢出,深层数据仍会崩。
- 误区:所有递归都能压成滚动变量;正解:多分支树形必须显式栈。
追问
- Q:树高怎么估算最坏? A:链形退化为 O(n)。
- Q:显式栈放哪里? A:堆上的 Deque,不受线程栈容量限制。
02.6.1.3-015 记忆化缓存会有什么副作用?
一句话结论
缓存把状态结果固定,若函数依赖外部可变状态、随机数或时间,缓存会返回陈旧结果;带副作用的递归不宜记忆化,缓存键也必须能区分外部状态变化。
概念解释
- 副作用:改外部变量、读外部环境。
- 陈旧:状态相同但外部已变。
原理流程
- 检查函数是否纯。
- 外部状态纳入缓存键或弃用缓存。
- 缓存只缓存无副作用计算。
代码 / 示例
依赖全局计数器的递归:复用缓存会跳过本应执行的计数副作用
常见误区
- 误区:memo 命中就不再执行函数体;正解:副作用应在缓存外完成。
- 误区:跨用例复用缓存不清空;正解:新用例需重置 memo。
追问
- Q:跨多组数据缓存怎么管理? A:每组用独立 memo 或用完清空。
- Q:缓存能存中间副作用结果吗? A:不能,缓存的是纯计算值。
02.6.1.3-016 记忆化复杂度口径怎么报?
一句话结论
时间 = 状态数 × 每个状态转移代价;空间 = 状态数(memo)+ 递归栈深;状态数由维度值域决定,转移代价看枚举的决策数。
概念解释
- 状态数:可达状态个数。
- 转移代价:单状态枚举分支数。
原理流程
- 数清状态维度值域。
- 乘单状态转移代价。
- memo 空间加栈深。
代码 / 示例
零钱兑换:状态 O(amount),每状态枚举 n 种币 → O(n·amount)
常见误区
- 误区:记忆化时间按递归树最坏估;正解:每个状态只算一次,按状态数估。
- 误区:漏掉递归栈空间;正解:memo 之外还要加栈深。
追问
- Q:状态稀疏怎么估空间? A:只缓存命中状态,用哈希表更省。
- Q:转移代价大怎么办? A:看内层循环分支数,逐项计入。
02.6.1.3-017 备忘录数组和哈希表怎么选?
一句话结论
状态下标连续、值域有限用数组,访问 O(1) 且省哈希开销;状态稀疏、值域大或维度非整数编码用哈希表;多维状态可先编码成整数键再入表。
概念解释
- 数组:连续下标、静态分配。
- 哈希:稀疏键、动态扩容。
原理流程
- 评估状态值域与连续性。
- 连续有限选数组。
- 稀疏/大范围选哈希。
代码 / 示例
int[] memo = new int[n]; // 下标 0..n-1
Map<Integer, Integer> memo2 = new HashMap<>(); // 稀疏
常见误区
- 误区:状态范围很大也开数组;正解:值域爆炸时数组不可行,用哈希或换思路。
- 误区:多维直接用嵌套哈希;正解:先编码成整数键更直接。
追问
- Q:数组初始化哨兵怎么定? A:结合合法值域选不冲突标记。
- Q:哈希键碰撞如何避免? A:编码保证唯一映射,或用对象键重写 equals/hashCode。
02.6.1.3-018 剪枝和记忆化怎么配合?
一句话结论
剪枝剔除确定无解分支,记忆化缓存可达状态结果;二者可叠加:先做安全剪枝减少进入分支,再对剩余状态缓存;注意剪枝条件不能破坏状态等价性,缓存键不含被剪掉的历史。
概念解释
- 剪枝:减少分支。
- 缓存:复用状态。
- 配合:先筛后存。
原理流程
- 入口剪枝非法状态。
- 查缓存复用。
- 未命中计算回填。
代码 / 示例
超 target 直接返回 → 查 memo → 计算并缓存
常见误区
- 误区:剪枝掉的状态也写入缓存;正解:无解哨兵可缓存,但要确认等价。
- 误区:缓存键与剪枝历史相关;正解:历史不影响后续时才可缓存。
追问
- Q:剪枝结果能缓存吗? A:确定性无解可以,标记不可行状态。
- Q:两者顺序? A:先判边界剪枝,再查缓存。
02.6.1.3-019 递归可读性与工程权衡怎么判断?
一句话结论
逻辑分层清晰、规模可控时用递归,代码短且贴合问题结构;深度大、栈紧张或团队规范要求时改迭代;面试先给递归思路与复杂度,再说明迭代改造点。
概念解释
- 可读性:递归贴近定义。
- 工程约束:栈深、性能、规范。
原理流程
- 先写递归表达思路。
- 评估深度与规模。
- 必要时给迭代版本。
代码 / 示例
树形/回溯:递归优先;长链/深层网格:迭代兜底
常见误区
- 误区:面试只交递归版不评估深度;正解:主动说明最坏深度与改造方向。
- 误区:为性能过早把所有递归改迭代;正解:先实测再优化。
追问
- Q:递归代码评审关注什么? A:终止条件、规模下降、现场恢复、复杂度。
- Q:迭代版怎么向面试官解释? A:对照递归帧说明显式栈保存的信息。
02.6.1.3-020 递归代码与迭代栈怎么对照排查?
一句话结论
列对照表:递归参数对应栈帧字段、递归调用对应压栈、返回合并对应出栈状态位;不一致处即为转换错误;先用小用例逐步打印栈内容核对顺序与结果。
概念解释
- 对照表:递归元素 ↔ 迭代结构。
- 逐步核对:帧进出顺序、合并值。
原理流程
- 逐行映射递归到栈帧。
- 小用例打印栈轨迹。
- 比对两版输出与顺序。
代码 / 示例
递归形参 → 帧字段
递归调用 → push 子帧
return 合并 → 出栈合并阶段
常见误区
- 误区:只对照最终结果不对照顺序;正解:访问/合并顺序错误会影响结果。
- 误区:栈帧字段漏补;正解:以原函数局部变量为准逐项核对。
追问
- Q:转换后结果不同先查什么? A:帧状态位与子帧压入顺序。
- Q:怎么保证迭代不溢出? A:显式栈在堆上,深度只受内存限制。