斐波那契数列+记忆化搜索
有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？ Input 输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。 Output 对于每个测试实例，请输出不同走法的数量 Sample Input 2 2 3 Sample Output 1 2 #include<stdio.h> int an[45]; int F(int m) { if(m==0||m==1) return 1; else { if(an[m]!=0) return an[m]; else { an[m]=F(m-1)+F(m-2); return an[m]; } } } int main() { int n; scanf("%d",&n); while(n--) { int m; an[0]=1; an[1]=1; scanf("%d",&m); if(m==1) printf("0\n"); else { m--; if(an[m]==0) { an[m]=F(m); printf("%d\n",an[m]); } else printf("%d\n",an[m]); } } return 0; }