◎学完你会
- 用「状态 / 转移 / 边界」三要素拆解任何 DP 题，先想清楚再写代码；
- 写最经典的爬楼梯：
dp[i]=dp[i-1]+dp[i-2]；
- 知道状态定义不清、转移漏边界是 DP 翻车的两大根源。
1动一动：爬楼梯填表
每次走 1 阶或 2 阶，爬到第 n 阶有几种走法？令 dp[i]=爬到第 i 阶的方法数，
则 dp[i]=dp[i-1]+dp[i-2]（最后一步跨 1 或 2 阶）。点「走一步」逐格填：
n = 6
dp[0]=1（原地，1 种）。点「走一步」从 dp[1] 开始填。
答案 = dp[n]。
2关键命令：DP 三要素
// ① 状态：dp[i] = 爬到第 i 阶的方法数
dp[0] = 1; dp[1] = 1; // ③ 边界：初值
for(i=2; i<=n; i++)
dp[i] = dp[i-1] + dp[i-2]; // ② 转移：最后一步跨 1 或 2 阶
任何 DP 先问自己三句：dp[i] 代表什么（状态）→ 从更小的问题怎么得到它（转移）→ 最小的 i 值是多少（边界）。
转移方向要对：算 dp[i] 只依赖比它小的 dp，别反着引用未来的状态。
⚠易错点
状态定义不清：说不清 dp[i] 是"方法数"还是"步数"，转移和答案全跟着错。
转移漏边界情况：i<2 时 dp[i-2] 越界，要单独处理初值。
边界初值设错：dp[0]、dp[1] 错一个，整个数列平移，答案全错。
数组开小 / 忘记取模：结果可能爆 int，按题意取模、按 n 开够数组。
?跨学科：DP 就是"由小到大攒答案"
理财的复利、银行的分期、几何里的递推数列，都是一步步由前一项推出下一项——
dp[i] 依赖更小的 dp，正是"规模由小到大"的递推。
斐波那契数列 1,1,2,3,5,8… 就是最朴素的 DP：每一项由前两项推出。
✎练一练
爬楼梯题里 dp[i] 的正确状态定义是？
状态定义是 DP 的根：dp[i] = 爬到第 i 阶的方法数，转移才是 dp[i-1]+dp[i-2]。
为什么
dp[i]=dp[i-1]+dp[i-2]？请说明它对应什么情况、覆盖是否完整。
答案：最后一步只有两种可能——从 i-1 跨 1 阶，或从 i-2 跨 2 阶。这两种情况互斥且穷尽了所有走法，所以方法数相加。这样 dp[i] 就由两个更小的子问题推出，形成完整覆盖、无重复。