直接应用递推公式打表。
附ac代码：
#include <stdio.h>
int main(){
int t, n, a[41] = {0, 0, 1, 2};
for(int i = 4; i != 41; ++i)
a[i] = a[i - 1] + a[i - 2];
scanf("%d", &t);
while(t-- && scanf("%d", &n))
printf("%d\n", a[n]);
return 0;
}原文：http://blog.csdn.net/chang_mu/article/details/19099067