什么时候该从记忆化搜索走向动态规划表

很多人做动态规划时会犹豫：

• 是先写递归 + 记忆化
• 还是直接写 DP 表

这其实不是谁更高级的问题，而是哪一种更适合当前理解阶段。

记忆化搜索的优点

如果你还在理解问题结构，记忆化搜索通常更自然：

• 先按直觉写递归
• 再把重复子问题缓存起来

这种方式更贴近“问题怎么拆”的过程。

DP 表的优点

当你已经明确：

• 状态是什么
• 转移是什么
• 遍历顺序是什么

这时写成 DP 表会更稳定，也更容易优化空间。

什么时候该切换

我一般会这样判断：

• 如果题意刚看懂，还不确定状态关系，先记忆化
• 如果转移已经稳定，开始考虑边界和空间优化，就转表格

为什么这个切换很重要

很多人卡在 DP，不是不会，而是上来就逼自己直接写表。

这样很容易在“状态没想清楚”的时候，同时被：

• 下标
• 边界
• 遍历顺序

一起拖住。

结论

记忆化搜索更像理解问题的桥梁，DP 表更像稳定实现的形式。

先后顺序搞对了，动态规划会顺很多。