记忆化优化DFS的核心是避免重复计算，通过哈希表缓存唯一状态键（如节点ID、(node, remaining_energy)、位掩码等）对应的结果，递归前查缓存、命中即返，未命中则计算后存储；需置于剪枝判断之后，并与可行性/最优性剪枝协同提升效率。
缓存优化深度优先搜索（DFS）的核心是避免重复计算相同子问题，尤其在存在重叠子结构的场景中——比如图中存在环、树有重复子树，或状态空间存在等价路径时。它不改变DFS的基本遍历逻辑，而是通过“记住已算过的结果”来跳过冗余分支。
用哈希表做记忆化存储
最常用方式是用字典（Python）或哈希映射（C++/Java）缓存输入状态到结果的映射。关键在于设计能唯一标识子问题的键：
- 对树/图节点遍历，若只关心“从某节点出发能否到达目标”，键可为节点ID；
- 若涉及路径约束（如带限制条件的路径计数），键需包含节点+当前状态变量，例如
(node, remaining_energy)； - 在排列组合类问题中，键常为冻结后的状态，如
tuple(sorted(current_subset))或位掩码mask（表示哪些元素已被选）。
在递归DFS中插入缓存检查
每次进入递归前先查缓存，命中则直接返回；未命中则计算后存入：
- 函数开头加
if (state) in memo: return memo[state]； - 递归调用返回后，执行
memo[state] = result； - 注意：缓存应放在所有剪枝判断之后，否则可能漏掉无效状态的记录，导致后续误判。
结合剪枝提升缓存效率
单独缓存不如与剪枝协同使用。例如在数独或N皇后中：
- 先按启发式顺序选择分支（如候选最少的格子），让更早命中缓存；
- 可行性剪枝（如当前行已冲突）应在缓存查询前执行，避免把非法状态写入缓存；
- 最优性剪枝（如当前代价已超最优解）可配合缓存，跳过整棵不可能改进的子树。
注意缓存粒度与内存开销
缓存不是越多越好，需权衡空间与收益：
- 粗粒度缓存（如整个子树根节点）节省空间但复用率低；
- 细粒度缓存（如
(node, depth, flag)三元组）复用率高，但键空间爆炸； - 对大规模静态图，可预计算并持久化常用子图结果；实时系统建议设LRU容量限制，防止内存溢出。
