罗罗编程学习记录
本页内容 展开查看

02.6.1.3 记忆化与递归转迭代

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归 / 02.6.1 递归与回溯框架

02.6.1.3-001 怎么识别重叠子问题?

一句话结论

递归展开后同一状态被多次计算,即存在重叠子问题;表现为递归树出现重复子树,朴素递归时间随重复次数指数膨胀,可用记忆化或 DP 消除。

概念解释

  • 状态:决定后续计算的输入参数组合。
  • 重复子树:相同状态再次出现。

原理流程

  1. 画递归树。
  2. 标记重复出现的节点。
  3. 重复越多,记忆化收益越大。

代码 / 图示

fib(4)
├ fib(3)
│ ├ fib(2)  ← 重复
│ └ fib(1)
└ fib(2)    ← 重复

常见误区

  • 误区:递归调用次数多就是重叠子问题;正解:必须是相同状态重复求解,不同状态不算。
  • 误区:树遍历有重叠子问题;正解:每个节点只访问一次,无重复。

追问

  • Q:重叠子问题是 DP 前提吗? A:是,配合最优子结构才可 DP。
  • Q:怎么快速判断? A:看递归参数是否反复取到相同组合。

02.6.1.3-002 记忆化搜索怎么实现?

一句话结论

用 memo 数组或哈希表缓存每个状态的结果;进入递归先查缓存,命中直接返回;未命中则计算并存入缓存后返回;状态键由影响结果的参数组成。

概念解释

  • memo:状态到结果的映射。
  • 命中:直接复用。
  • 未命中:计算并回填。

原理流程

  1. 进入函数先查 memo。
  2. 未命中执行递归计算。
  3. 结果写入 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 数组按顺序递推,无递归栈、易空间优化;状态转移清晰后通常改自底向上。

概念解释

  • 自顶向下:从原问题递归到基准。
  • 自底向上:从基准递推到原问题。

原理流程

  1. 先写递归思路。
  2. 加 memo 验证状态。
  3. 再按依赖顺序填表。

代码 / 示例

斐波那契:递归 memo 自上而下;数组 f[0..n] 自下而上

常见误区

  • 误区:自底向上必须先想透递归;正解:可直接按状态定义填表。
  • 误区:两种方式遍历顺序相同;正解:方向相反,依赖状态先算。

追问

  • Q:哪种更省栈? A:自底向上无递归栈。
  • Q:哪种更容易剪枝? A:自顶向下可在不命中分支提前返回。

02.6.1.3-004 记忆化和 DP 是什么关系?

一句话结论

记忆化搜索是自顶向下的 DP:状态定义、转移方程与自底向上 DP 完全相同,区别只是计算方向;memo 数组对应 DP 表,缓存命中对应查表。

概念解释

  • 状态:memo 键 / DP 下标。
  • 转移:递归关系 / 递推方程。
  • 基准:memo 基准值 / DP 初始化。

原理流程

  1. 确定状态与转移。
  2. 递归版加缓存。
  3. 等价改写为填表版。

代码 / 示例

memo[i] = f(memo[...])  ↔  dp[i] = f(dp[...])

常见误区

  • 误区:记忆化不算 DP;正解:它是 DP 的递归实现形式。
  • 误区:记忆化缓存的是路径;正解:通常缓存状态值,路径另存。

追问

  • Q:什么时候保留递归 memo 写法? A:状态稀疏、只访问部分状态时。
  • Q:DP 表满填但状态很少怎么办? A:记忆化更省未访问状态。

02.6.1.3-005 缓存状态怎么设计?

一句话结论

缓存键必须包含所有影响后续结果的参数:下标、剩余容量、剩余和、位置状态等;值存该状态下的最优值/计数/可行性;维度多时用多维数组或编码成整数/字符串键。

概念解释

  • 状态维度:决定结果的全部输入。
  • 键编码:多维压成数组下标或整数。

原理流程

  1. 列出影响结果的参数。
  2. 确定值域选数组或哈希。
  3. 定义缓存值含义。

代码 / 示例

// 二维状态:(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 包装区分“未计算”与“结果为负”。

概念解释

  • 哨兵值:表示未缓存。
  • 冲突:合法结果等于哨兵。

原理流程

  1. 选不冲突的哨兵。
  2. 初始化全部为哨兵。
  3. 命中判断后再取值。

代码 / 示例

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 什么场景记忆化不能用?

一句话结论

当结果依赖完整历史路径(已选集合、路径顺序、访问过的具体元素),而历史无法被有限状态维度表达时,记忆化会把不同历史误判为同一状态;此时只能回溯枚举。

概念解释

  • 路径依赖:历史选择影响后续。
  • 状态不可约:历史无法压缩成少量维度。

原理流程

  1. 检查后续选择是否只依赖当前状态。
  2. 若依赖已选集合/顺序,缓存失真。
  3. 保留回溯枚举。

代码 / 示例

排列枚举:历史顺序不同即不同解,memo 无法合并

常见误区

  • 误区:把路径本身当缓存键;正解:路径长度随规模增长,缓存失去意义。
  • 误区:认为加了 memo 就一定提速;正解:状态不可缓存时反而增加开销。

追问

  • Q:子集和计数能记忆化吗? A:状态 (下标, 剩余和) 可缓存,与具体选法无关时可以。
  • Q:棋盘摆放能缓存吗? A:占用布局是状态,规模小可掩码缓存。

02.6.1.3-008 递归转迭代:显式栈模拟的基本思路?

一句话结论

把递归帧的参数、局部变量、返回位置压入显式栈;弹出时按状态位判断是首次进入还是子节点已返回,首次进入则压回本帧并压子帧,返回阶段做合并。

概念解释

  • 帧对象:参数 + 局部 + 状态位。
  • 状态位:待进入 / 子节点已完成。

原理流程

  1. 构造根帧压栈。
  2. 弹出帧,按状态位处理。
  3. 需要子问题则压回本帧再压子帧。

代码 / 示例

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 迭代栈里要保存哪些帧信息?

一句话结论

保存递归函数的入参、本层局部变量、当前执行位置(返回点);合并阶段需要的子结果也要随帧保留;对照原递归函数的参数表与局部变量逐项列出。

概念解释

  • 入参:递归参数。
  • 局部:本层中间值。
  • 返回点:执行到第几个子调用。

原理流程

  1. 读原递归函数参数与局部。
  2. 映射为帧字段。
  3. 合并阶段从帧内取子结果。

代码 / 示例

帧:{入参 i, 左子结果, 右子结果, 状态位}

常见误区

  • 误区:遗漏本层局部变量;正解:合并时用到的中间值必须随帧保存。
  • 误区:把子结果存在全局变量;正解:多分支下应挂在各自帧上。

追问

  • Q:帧对象怎么定义? A:内部类含参数字段与状态枚举。
  • Q:迭代栈空间多少? A:与递归栈深同阶 O(h)。

02.6.1.3-010 后序类问题怎么转迭代栈?

一句话结论

后序需要左右子树结果返回后再处理当前节点;迭代时先压当前帧标记“待合并”,再压右子帧、左子帧;子帧全部弹出后,当前帧进入合并阶段读取子结果。

概念解释

  • 后序:左右根。
  • 栈序:先压右后压左,保证左先出。

原理流程

  1. 压根帧待合并。
  2. 弹出待合并帧时压回并压子帧。
  3. 子帧完成后回到本帧合并。

代码 / 示例

push(root, 待合并)
pop → push(self, 合并) → push(right) → push(left)

常见误区

  • 误区:先压左后压右;正解:栈 LIFO,要左先出须先压右。
  • 误区:合并阶段重复访问子节点;正解:子结果已存帧内,直接读取。

追问

  • Q:二叉树后序迭代常用什么标记? A:访问标记或记录上次访问节点。
  • Q:树形 DP 能这样转吗? A:能,帧内保存左右子树返回值。

02.6.1.3-011 回溯怎么迭代化?

一句话结论

显式栈保存当前路径与候选下标;每帧记录已尝试到第几个选择,弹出时撤销本层选择并推进下一个候选;等价于把递归调用栈换成手动栈,路径仍需做选择/撤销。

概念解释

  • 栈帧:路径 + 当前候选位置。
  • 撤销:出栈时移除本层选择。

原理流程

  1. 压根帧。
  2. 取帧候选,合法则加入路径压子帧。
  3. 帧耗尽出栈并撤销。

代码 / 示例

栈元素:{路径, start}
候选耗尽 → 路径弹出末位 → 父帧推进候选

常见误区

  • 误区:迭代回溯不需要撤销;正解:路径复用,出栈仍要恢复。
  • 误区:候选指针忘记推进;正解:每帧记录尝试到的下标,避免死循环。

追问

  • Q:迭代回溯可读性如何? A:较差,工程上递归优先,栈深受限再迭代。
  • Q:收集结果时机变吗? A:不变,到达结束条件即拷贝路径。

02.6.1.3-012 递归转迭代的代价怎么对比?

一句话结论

迭代省去调用栈但需手动管理帧与状态位,代码复杂度上升;空间上迭代用显式栈与递归栈同阶,部分场景可滚动变量压到 O(1);选择取决于栈深约束与可读性要求。

概念解释

  • 调用开销:递归帧压弹。
  • 手动管理:帧结构与状态机。
  • 空间:显式栈 vs 递归栈。

原理流程

  1. 评估递归深度是否越界。
  2. 估算迭代帧字段数量。
  3. 在可读性与约束间取舍。

代码 / 示例

斐波那契:递归 O(n) 栈 → 滚动变量 O(1) 空间

常见误区

  • 误区:迭代一定省空间;正解:显式栈仍占 O(h),只有可滚动状态才能压空间。
  • 误区:转换后代码一定更短;正解:状态机写法通常更长。

追问

  • Q:什么情况必须转迭代? A:递归深度可能溢出的长链/深层网格。
  • Q:迭代版怎么验证等价? A:小用例对比两版输出。

02.6.1.3-013 函数式递归与命令式迭代怎么对照?

一句话结论

函数式递归靠表达式组合结果,状态不可变;命令式迭代靠循环变量原地更新;对照时把递归的“子结果合并”翻译成循环里对累积变量的更新。

概念解释

  • 函数式:纯表达式、无共享可变状态。
  • 命令式:循环修改变量。

原理流程

  1. 识别递归的累积量。
  2. 映射为循环变量初值与更新式。
  3. 基准映射为循环退出条件。

代码 / 示例

// 递归:sum = a[i] + sum(i+1)
// 迭代:acc = 0; 从后往前 acc += a[i]

常见误区

  • 误区:递归的返回值直接对应一个循环变量;正解:多分支合并可能需要多个累积量。
  • 误区:方向照搬;正解:自顶向下递归常对应反向迭代。

追问

  • Q:尾递归最容易翻译成什么? A:循环加累积参数。
  • Q:不可变优势是什么? A:无共享状态副作用,便于推理。

02.6.1.3-014 栈溢出风险下怎么改造?

一句话结论

先估算最坏递归深度;接近上限时优先改迭代(显式栈或滚动变量),或改分治降低树高;不要依赖运行环境尾递归优化,也不应只靠调大栈容量掩盖问题。

概念解释

  • 最坏深度:最长调用链。
  • 改造方向:迭代化、扁平化、平衡化。

原理流程

  1. 评估深度与栈容量。
  2. 可滚动则改循环。
  3. 树形则显式栈或平衡划分。

代码 / 示例

长链表递归反转 → 三指针迭代
深层网格 DFS → 显式栈 DFS

常见误区

  • 误区:调大线程栈就能上线;正解:只是推迟溢出,深层数据仍会崩。
  • 误区:所有递归都能压成滚动变量;正解:多分支树形必须显式栈。

追问

  • Q:树高怎么估算最坏? A:链形退化为 O(n)。
  • Q:显式栈放哪里? A:堆上的 Deque,不受线程栈容量限制。

02.6.1.3-015 记忆化缓存会有什么副作用?

一句话结论

缓存把状态结果固定,若函数依赖外部可变状态、随机数或时间,缓存会返回陈旧结果;带副作用的递归不宜记忆化,缓存键也必须能区分外部状态变化。

概念解释

  • 副作用:改外部变量、读外部环境。
  • 陈旧:状态相同但外部已变。

原理流程

  1. 检查函数是否纯。
  2. 外部状态纳入缓存键或弃用缓存。
  3. 缓存只缓存无副作用计算。

代码 / 示例

依赖全局计数器的递归:复用缓存会跳过本应执行的计数副作用

常见误区

  • 误区:memo 命中就不再执行函数体;正解:副作用应在缓存外完成。
  • 误区:跨用例复用缓存不清空;正解:新用例需重置 memo。

追问

  • Q:跨多组数据缓存怎么管理? A:每组用独立 memo 或用完清空。
  • Q:缓存能存中间副作用结果吗? A:不能,缓存的是纯计算值。

02.6.1.3-016 记忆化复杂度口径怎么报?

一句话结论

时间 = 状态数 × 每个状态转移代价;空间 = 状态数(memo)+ 递归栈深;状态数由维度值域决定,转移代价看枚举的决策数。

概念解释

  • 状态数:可达状态个数。
  • 转移代价:单状态枚举分支数。

原理流程

  1. 数清状态维度值域。
  2. 乘单状态转移代价。
  3. memo 空间加栈深。

代码 / 示例

零钱兑换:状态 O(amount),每状态枚举 n 种币 → O(n·amount)

常见误区

  • 误区:记忆化时间按递归树最坏估;正解:每个状态只算一次,按状态数估。
  • 误区:漏掉递归栈空间;正解:memo 之外还要加栈深。

追问

  • Q:状态稀疏怎么估空间? A:只缓存命中状态,用哈希表更省。
  • Q:转移代价大怎么办? A:看内层循环分支数,逐项计入。

02.6.1.3-017 备忘录数组和哈希表怎么选?

一句话结论

状态下标连续、值域有限用数组,访问 O(1) 且省哈希开销;状态稀疏、值域大或维度非整数编码用哈希表;多维状态可先编码成整数键再入表。

概念解释

  • 数组:连续下标、静态分配。
  • 哈希:稀疏键、动态扩容。

原理流程

  1. 评估状态值域与连续性。
  2. 连续有限选数组。
  3. 稀疏/大范围选哈希。

代码 / 示例

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 剪枝和记忆化怎么配合?

一句话结论

剪枝剔除确定无解分支,记忆化缓存可达状态结果;二者可叠加:先做安全剪枝减少进入分支,再对剩余状态缓存;注意剪枝条件不能破坏状态等价性,缓存键不含被剪掉的历史。

概念解释

  • 剪枝:减少分支。
  • 缓存:复用状态。
  • 配合:先筛后存。

原理流程

  1. 入口剪枝非法状态。
  2. 查缓存复用。
  3. 未命中计算回填。

代码 / 示例

超 target 直接返回 → 查 memo → 计算并缓存

常见误区

  • 误区:剪枝掉的状态也写入缓存;正解:无解哨兵可缓存,但要确认等价。
  • 误区:缓存键与剪枝历史相关;正解:历史不影响后续时才可缓存。

追问

  • Q:剪枝结果能缓存吗? A:确定性无解可以,标记不可行状态。
  • Q:两者顺序? A:先判边界剪枝,再查缓存。

02.6.1.3-019 递归可读性与工程权衡怎么判断?

一句话结论

逻辑分层清晰、规模可控时用递归,代码短且贴合问题结构;深度大、栈紧张或团队规范要求时改迭代;面试先给递归思路与复杂度,再说明迭代改造点。

概念解释

  • 可读性:递归贴近定义。
  • 工程约束:栈深、性能、规范。

原理流程

  1. 先写递归表达思路。
  2. 评估深度与规模。
  3. 必要时给迭代版本。

代码 / 示例

树形/回溯:递归优先;长链/深层网格:迭代兜底

常见误区

  • 误区:面试只交递归版不评估深度;正解:主动说明最坏深度与改造方向。
  • 误区:为性能过早把所有递归改迭代;正解:先实测再优化。

追问

  • Q:递归代码评审关注什么? A:终止条件、规模下降、现场恢复、复杂度。
  • Q:迭代版怎么向面试官解释? A:对照递归帧说明显式栈保存的信息。

02.6.1.3-020 递归代码与迭代栈怎么对照排查?

一句话结论

列对照表:递归参数对应栈帧字段、递归调用对应压栈、返回合并对应出栈状态位;不一致处即为转换错误;先用小用例逐步打印栈内容核对顺序与结果。

概念解释

  • 对照表:递归元素 ↔ 迭代结构。
  • 逐步核对:帧进出顺序、合并值。

原理流程

  1. 逐行映射递归到栈帧。
  2. 小用例打印栈轨迹。
  3. 比对两版输出与顺序。

代码 / 示例

递归形参 → 帧字段
递归调用 → push 子帧
return 合并 → 出栈合并阶段

常见误区

  • 误区:只对照最终结果不对照顺序;正解:访问/合并顺序错误会影响结果。
  • 误区:栈帧字段漏补;正解:以原函数局部变量为准逐项核对。

追问

  • Q:转换后结果不同先查什么? A:帧状态位与子帧压入顺序。
  • Q:怎么保证迭代不溢出? A:显式栈在堆上,深度只受内存限制。