重复状态剪枝

一句话理解

重复状态剪枝：同样局面只搜一次。

为什么要学

记忆化、vis。

讲解

哈希或数组记下该状态最好结果。再遇到直接返回。

这是搜索和 DP 的交界。

例子

记忆化搜索就是带重复状态剪枝的 DFS。

常见错误

• 状态哈希冲突没处理。
• 该状态结果依赖路径却当全局 vis。