什么是状态

一句话理解

DP 的状态是把问题压缩后还够推下一步的信息。

为什么要学

DP 第一问：状态是什么。

讲解

例如 f[i] 表示前 i 个的答案。维数越多越细，也越慢。

例子

背包：考虑到第 i 件物品、容量还剩 j。

常见错误

• 状态少了推不动。
• 状态多了 TLE/MLE。