计数与概率 · 末步分类
先问“最后一步是什么”，再让状态保留下一步所需的信息。
视频加载失败，请确认assets文件夹完整，或直接打开MP4。正文与分章讲解仍可阅读。
自拟问题：从地面出发，每次只向上跨1级或2级，恰好到达第4级。不同的步长顺序算不同走法。共有几种？如果不允许连续两次跨2级，答案怎样变化？
第1步 / 共5步：明确计数对象
每条走法是由1和2组成、总和为4的有序序列。下一步先找末步为1的走法。
对应左侧4级台阶演示
等待分类
1、2、1与2、1、1是不同顺序，应分别计数。
演示只处理4级；例题的8级答案在正文逐级推出。
理解加法原理、乘法原理和有序序列；会列表枚举小规模情况。递推（recurrence）用较小规模的已知计数确定更大规模的计数。状态（state）是为了判断后续合法性而保留的信息。
本页S班深度是项目编排，非已核实的机构课纲。固定模型为离散台阶，每次1或2级，只向上，不越过终点；每个步长序列视为一种走法。图示不按实物比例。
设 f(n) 表示恰好走到第 n 级的走法数，其中 n 是非负整数。对于 n≥2，每条走法的最后一步只能是1或2，两种情况互斥且覆盖全部方案。
为什么零级是1？什么都不走是唯一的空序列。它是可以接上后续步子的合法起点，不表示走了一步。若误写 f(0)=0，就会把“直接跨2级”的那种走法漏掉。也可从 f(1)=1、f(2)=2 开始，但递推式此时只在 n≥3 使用。不要混用起点和适用下标。
直接在所有到第 n−2 级的方案后接2，可能形成末尾的2、2。原式已不能保证合法。将合法方案分为 A(n)：末步为1；B(n)：末步为2。总数 g(n)=A(n)+B(n)。
A(n)=A(n−1)+B(n−1)（n≥1）
前面末步是什么都可以。删去新接的1，可唯一恢复来源。
B(n)=A(n−2)（n≥2）
前一末步必须为1。只从A类接2，避免形成连续两个2。
为统一处理“直接从地面跨2级”，约定 A(0)=1、B(0)=0：把空方案放入可接2的起始类，这只是起始约定，不声称空方案真的以1结尾。另设 B(1)=0，A(1)=1。n≥1时两类才按实际末步解释；不计算负下标。
于是 A(n)=g(n−1)。当 n≥3，B(n)=A(n−2)=g(n−3)，得到压缩形式：
两条递推各有适用下标。先用状态转移证明，再压缩公式；不能看到前几个数就猜一个相似数列。
例题与练习均为自拟题。每张表的计数均用独立枚举核对。
例题一 · 普通末步递推
从地面出发，只向上，步长顺序不同算不同走法，不限制连续跨2级。求走法总数。
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| f(n) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |
答案：34种。其中末步1有 f(7)=21 种，末步2有 f(6)=13 种，合计34。独立核对：按跨2级的次数 k=0、1、2、3、4 分组，分别有1、7、15、10、1种，合计34；例如 k=2 时一共6步，从6个位置选2个放2，共15种。
例题二 · S班结构变式
其余条件同例题一。注意1、2、1、2合法，2、2、1不合法；限制针对相邻步长，非“只能用一次2”。
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| A(n) | 1 | 1 | 1 | 2 | 3 | 4 | 6 | 9 | 13 |
| B(n) | 0 | 0 | 1 | 1 | 1 | 2 | 3 | 4 | 6 |
| g(n) | 1 | 1 | 2 | 3 | 4 | 6 | 9 | 13 | 19 |
答案：13+6=19种。独立检查可按2的个数分组：没有2为1种；一个2为7种；两个2需在4个1形成的5个空隙中选2处，为10种；三个2与两个1只能为2、1、2、1、2，为1种；四个2不合法。共1+7+10+1=19种。
从地面出发，每次上1或2级，恰好到第7级，顺序不同算不同走法，不限制连续跨2级。共有几种？其中末步为2有几种？
普通递推 f(n)=f(n−1)+f(n−2)。从1、1开始，算到 f(5)=8、f(6)=13，所以 f(7)=13+8=21种。末步为2，删去它后恰好到第5级，有8种。末步为1有13种，两类相加21。
每次上1或2级，恰好到第7级，不能连续跨2级，步长顺序不同算不同方案。共有几种？其中末步为2有几种？
沿用受限状态：A(6)=6、B(6)=3，所以 A(7)=6+3=9。B(7)=A(5)=4。总数9+4=13种，其中末步为2有4种。
不能将末步2计为 g(5)=6，因为其中以2结尾的2种方案再接2会违法。压缩式也给出 g(7)=g(6)+g(4)=9+4=13。
| 误区或变化 | 为何不成立／怎样处理 |
|---|---|
| 把 f(0) 写成0 | 漏掉空方案，直接跨2级也会漏计。普通 f(2) 应为2。 |
| 末步1类与末步2类相乘 | 每条方案只属于其中一类，应相加；乘法用于依次选择。 |
| 受限走法继续用普通递推 | 四级最小反例：22被误计，普通5种，受限4种。 |
| 顺序无关，也套 f(n) | 四级时只按1和2的个数区分，仅有1111、112、22三类，已非5种。 |
| 允许后退、步长改为1或3、终点不可踩等 | 计数对象或转移改变，必须重新定义状态与边界；允许无限往返还可能有无限多种走法。 |
检查链：定义对象与规模 → 保留必要状态 → 证明分类互斥完备 → 证明可逆对应 → 写足初值与下标范围 → 小规模枚举核对。
完整文字稿默认展开；点击标题可定位到对应讲解。
四级台阶，每次上一级或两级，顺序不同算不同走法。先不要猜公式。
看最后一步。若最后上一级，删去它，就和三级台阶的走法一一对应，共三种。
若最后上两级，删去它，剩两级台阶的两种走法。两类不重不漏，所以共有五种。
记上到第n级的走法数为f。它等于前一级与前两级的走法数之和。零级有一种空方案，一级有一种。
如果不能连续上两级，走法二、二就不合法。此时不能直接沿用原来的递推式。
分为末步一级的A类与末步两级的B类。接一级可来自两类；接两级只能来自前两级的A类。
约定A零为一，B零与B一为零。逐级算出四级有四种，八级有十九种。先定状态，再验初值与转移。