动态规划的本质：无后效性与状态设计

什么是无后效性？

动态规划常被概括为“记住历史、推导未来”。但更关键的一点是：过去的决策是如何被记录的？

如果某一个阶段的最优策略取决于我们具体是如何走到这个状态的，那么这个状态就不具备“无后效性”，也就无法直接写出转移方程。 反之，只要当前状态能把所有会对未来产生影响的历史信息全部概括封存，未来就可以只基于当前状态展开推导。

状态设计的降维思考

设计状态时，可以遵循这三步：

1. 最小充分信息集：为了做出下一步决策，我最少需要知道当前所处位置的什么指标？（例如：当前下标 $i$、剩余背包容量 $j$、上一位填了什么数 $last$）。
2. 转移的拓扑序：状态之间必须能排成有向无环图（DAG）。每一个待求状态 $dp[i]$ 依赖的子状态必须在计算它之前就已经求出。
3. 空间滚动的可行性：如果 $dp[i]$ 只依赖于 $dp[i-1]$，往往可以通过滚动数组或倒序枚举将空间从 $O(n\times m)$ 优化到 $O(m)$。

记忆化搜索与递推的取舍

• 记忆化搜索（Top-down）：从大问题出发递归求子问题，只计算可达状态，对稀疏状态图更友好，编写自然。
• 循环递推（Bottom-up）：拓扑序通常清晰，无函数调用开销，常数更小，容易进一步配合前缀和、单调队列、斜率优化等技巧。

遇到困难时，先写出清晰的递归搜索 + 记忆化，往往是理清状态转移关系的最佳起点。