SSOJ1344爬楼梯
2413+
作者:crxis 发布:2017-06-23 分类:递推
题目大意:上楼梯,每次智能上一阶或者两阶,n阶台阶有多少种走法?(提示:斐波拉契数列)
题目描述
小明家外面有一个长长的楼梯,共N阶。小明的腿很长,一次能跨过一或两阶。有一天,他突发奇想,想求出从最低阶到最高阶共有几种爬楼梯的方案。你帮帮他吧!
输入
一个整数N。
输出
一个整数,为方案总数。
样例输入
5
样例输出
8
提示
0≤N≤40
解题思路
到达台阶n,可以由n-1阶或者n-2阶到达,故f[n] = f[n-1] + f[n-2]。前面几个台阶可以预先赋初值,然后梯队得到n阶台阶的走法。