DP：先看状态

动态规划最难、也最关键的一步，是定义状态——想清楚"我要用一个什么样的量，来记录一个子问题的答案"。状态定对了，转移方程往往自己就浮现出来；定错了，怎么推都别扭。

以爬楼梯为例（每次上 1 级或 2 级，问上到第 $n$ 级有多少种走法），状态就定成：

$$dp[i]=\text{到达第 }i\text{ 级的不同走法数}$$

int dp[N];
// dp[i] 表示走到第 i 级台阶的方案数

定状态时问自己三句话：这个量要描述哪个子问题？它需要几个下标（几维）？它存的是最优值、方案数还是可行性？比如背包的状态是 $dp[i][j]$（前 $i$ 件、容量 $j$ 下的最大价值），比爬楼梯多一维，因为它要同时记住"看了几件"和"还剩多少容量"。

坑：状态定得太少会漏信息（推不下去），定得太多会爆内存。先从"答案是什么"倒推需要记住哪些信息，刚好够用即可。这一步想清楚，DP 就成功了一半。