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

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

对于第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种走法

这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法…… 　　1，2，3，5，8，13……所以，登上十级，有89种走法。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息