状态与转移

写任何 DP，先把三件事想清楚，代码几乎是顺带的。

状态：dp[i] 表示什么

状态要能覆盖答案，信息还要足够推出下一步。爬楼梯里，dp[i] = 到第 i 阶的走法数。

转移：dp[i] 怎么由更小的状态算出

转移方程要不重不漏——每种情况恰好算一次。爬楼梯的转移就是：

$$d{p}_i=d{p}_{i-1}+d{p}_{i-2}$$

边界：递推的起点

$d{p}_1=1$（一种走法）、$d{p}_2=2$（1+1 或 2）。边界错了，后面全错。

"状态 + 转移 + 边界"是所有 DP 的三件套。拿到新题先别急着敲代码，先在纸上把这三样填出来——想清楚了，题就做完一大半。