#include<bits/stdc++.h>
using namespace std;
int main ()
{
	int n,m,i;
	int a[45];a[1] = 1,a[2] = 1;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&m);
     	for(i = 3;i<=m;i++)
     	a[i] = a[i-1]+a[i-2];
        printf("%d\n",a[m]);
	}
	return 0;
 } 

不妨令n级楼梯有a[n]种方法，则考虑有哪几种方法可以到达第n级楼梯，易知：可从n-1级直接上，亦可从n-2级跨两级上，因此该递归公式为
a[i] = a[i-1]+a[i-2]；
添加链接描述