动态规划中memoization与tabulation两种思路的核心差异咨询

把“是否使用递归”作为二者的核心区分标准是完全错误的——递归/迭代只是实现手段，不是本质差异，两种方法都可以用递归或者迭代实现，核心区别完全在计算逻辑层面。

核心差异点 #

• 子问题触发逻辑不同
  Memoization是需求驱动的懒计算：从原问题出发，只有求解当前问题确实需要用到某个子问题的结果时，才会触发对应子问题的计算，没有被依赖链覆盖的子问题永远不会被计算。哪怕递归实现时会先下钻到基准case，下钻路径也完全由原问题的依赖关系决定，不会遍历所有可能的子问题。比如凑硬币问题中求解凑100元的最优解，memoization不会计算凑3元这类不在最优解依赖路径上的子问题。
  Tabulation是顺序驱动的预计算：需要提前划定所有可能用到的子问题范围，按照子问题规模从小到大的顺序逐一计算填充表格，不管某个子问题的结果会不会被最终的原问题用到，只要在划定范围内都会被提前算完。还是以凑100元的问题为例，tabulation会从0元、1元、2元一直算到100元，哪怕3元的结果和最终最优解完全无关，也会被提前计算存入表中。

• 计算顺序的约束强度不同
  Memoization不需要开发者提前明确子问题的计算顺序，只要在代码中定义清楚“当前问题依赖哪些子问题”即可，运行时会自动沿着依赖关系查找缓存：缓存命中直接返回结果，未命中就先计算对应子问题。遇到树形DP、状态依赖为非线性网状结构的场景时，memoization的实现成本极低，不需要额外梳理子问题的拓扑排序。
  Tabulation要求开发者必须在编码阶段就确定所有子问题的拓扑顺序，严格保证计算某个子问题时，它依赖的所有前置子问题结果已经完成计算。如果子问题依赖关系复杂，很容易因为遍历顺序错误导致逻辑bug。

你观察到的“memoization会先触达基准case再向上推导，和tabulation从底层子问题往上算的过程相似”是观察粒度过粗导致的错觉。二者虽然最终都是通过基准case的结果逐层推导得到原问题答案，但memoization的计算路径是原问题依赖链的逆序，仅覆盖必要的子问题分支；tabulation的计算路径是开发者提前定义的全量子问题遍历顺序，覆盖预设范围内的所有子问题，这是二者最容易被忽略的执行层本质区别。

常见误区澄清 #

“memoization必须用递归、tabulation必须用迭代”是完全错误的刻板认知：

• 你完全可以用迭代手动维护栈结构实现memoization，逻辑和递归版本完全一致，只是没有使用编程语言自带的递归栈而已，本质还是需求驱动的懒计算
• 你也可以用递归实现tabulation，只要逻辑是按顺序预计算所有子问题，哪怕用递归做遍历，本质还是tabulation

实际选型参考 #

• 如果子问题空间存在大量不会被原问题用到的冗余子问题，或者子问题依赖关系复杂、很难梳理出线性遍历顺序，优先选memoization，实现成本低、逻辑不容易出错，还能跳过不必要的计算
• 如果绝大多数子问题都会被原问题用到，且子问题依赖顺序规整（比如线性DP、背包类问题），优先选tabulation，没有递归栈的额外开销，运行常数更低，也更方便做滚动数组类的空间优化

内容的提问来源于stack exchange，提问作者jojo33