超级台阶
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
-
有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第m级，共有多少走法？
注：规定从一级到一级有0种走法。
- 输入
- 输入数据首先包含一个整数n(1<=n<=100)，表示测试实例的个数，然后是n行数据，每行包含一个整数m，（1<=m<=40), 表示楼梯的级数。
- 输出
- 对于每个测试实例，请输出不同走法的数量。
- 样例输入
-
2
2
3 - 样例输出
-
1
2
一开始考虑的是深度优先搜素，但是发现会有很多重复的搜索过程，比如第一步1阶第二步2阶和第一步2阶第二部1阶，这两种情况后面的走法完全一样，但是搜索的话会向下走到底2次，所以想到了递推，对于每一阶台阶 i 来说，能直接到达的位置只有i - 1和i - 2，那么i的总的方法数应该是i - 1和i - 2的方法数之和，而这个公式恰好是斐波那契数列，一切就简单了
#include<stdio.h>
int main()
{
int array[40] = {1};
int i , j , k; array[1] = 1;
for(i = 2 ; i < 40 ; i++)
{
array[i] = array[i - 2] + array[i - 1];
}
array[0] = 0;
scanf("%d" , &i);
while(i--)
{
scanf("%d" , &j);
printf("%d\n" , array[j - 1]);
}
return 0;
}