递推法

楼梯一步能迈 1 或 2 级，第 n 级的方法数 = 第 n−1 级（再跨 1）+ 第 n−2 级（再跨 2）。把“第 n 的答案”表达成“更小规模的答案”，就能像多米诺一样推过去。

1. 1设 a_n 为规模为 n 时的方案数。
2. 2分析“最后一步”，把它拆成几种情形，每种情形剩下的规模分别是 n − k。
3. 3于是 a_n = a_{n-1} + a_{n-2} + …（看实际情形）。
4. 4结合初值 a_0, a_1 从小到大算出 a_n。

• 初值算错，整条链都错。
• “分析最后一步”时情形不要漏。