Question

每一步只能上一级或三级台阶，要登上第10级台阶，共有几种不同的走法

Answer 1

解：
只有1级台阶有1种走法；
只有2级台阶有2种走法；
只有3级台阶有3种走法；
只有4级台阶有5种走法（迈第1步时可跨1级，也可跨2级，即分成两类：第1步跨1级哗裤兄还剩3级，上面已知3级台阶有3种走法；第1步跨2级还剩2级，上面已知乱袭2级台阶有2种走法，∴4级台阶共有3＋2＝5种走法。其递推纯腔公式为这一项等于前两项的和）
规律为：
级数
1
2
3
4
5
6
7
8
9
10
走法
1
2
3
5
8
13
21
34
55
89
共有89不同的走法

Answer 2

对于第N级台阶，上一步要么在第N-1级台阶，要么在第N-3级台阶
因此设第N级台阶的走法是f(N)，得到f(N)
=
f(N-1)
+
f(N-3)
特别地，初始状态视为第0级台阶，有f(0)=1
因此得到：f(1)
=
1
【因为1<3，所以f(N-3)不存在者橡，同时，显然第一级台阶只有一种走法】，
f(2)
=
1
【同样如银，第二级也只能1+1的形式首橡旁去走】
f(3)
=
f(2)
+
f(0)
=
2
【可以1+1+1，也可以一步直接走3】
依次类推：
f(4)
=
3;
f(5)
=
4
;
f(6)
=
6;
f(7)
=
9;
f(8)
=
13;
f(9)
=
19;
f(10)
=
28
因此一共28种走法