动态规划中的状态压缩

这页是提醒自己，在追求更复杂转移之前，先看看状态能不能简化。

检查清单

• 先判断转移是否只依赖 i - 1。
• 再看状态能不能压成一维数组。
• 最后决定循环应该正向还是反向，避免覆盖还要用到的值。

常见场景

这类技巧常出现在背包型 DP、子序列计数和局部依赖的网格转移里。