教学楼的楼梯 数组做法（C语言代码）

解题思路:

从第一层阶梯开始，我们试着列一下不同走法：

2层： 1,1；     2；   共2种；

3层： 1,1,1;     1,2;      2,1;    共3种；

4层： 1,1,1,1；    1,1,2；    1,2,1；    2,1,1；    2,2；    共5种；

5层： 1,1,1,1,1;    1,1,1,2;    1,1,2,1;    1,2,1,1    2,1,1,1;    2,1,2;    2,2,1;    1,2,2;    共8种；
从中我们可以发现规律，其实题目的意思就是斐波那数列，即从第三项开始，每一项等于前两项的和，刚开始我试了用递归算法，但是无奈内存超限，然后用了数组的做法，先计算出斐波那数列前40项并存入数组里，然后再按需输出。看懂了希望能给个赞，有想法可以在评论区留言。

注意事项:
是从第一层阶梯开始走的，所以套进数组M要减1，并且当M为1时要输出1！！！（我因为这里错了好久）
参考代码:

#include<stdio.h>
int main()
{
	int N,M,i;
	long long k[40]={1,1,2};
	scanf("%d",&N);
	for(i=3;i<40;i++)
	{
		k[i]=k[i-1]+k[i-2];
	}
	while(N--)
	{
		scanf("%d",&M);
		if(M>40||M<1)
			printf("0\n");
		else 
			printf("%lld\n",k[M-1]);
	}
	return 0;
}