超级楼梯

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 55367    Accepted Submission(s): 28142 Problem Description 有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？   Input 输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。   Output 对于每个测试实例，请输出不同走法的数量   Sample Input 2 2 3   Sample Output 1 2   Author lcy   Source 2005实验班短学期考试   Recommend lcy 开始我是用回溯法，把这个问题抽象成完全二叉树，每次有两条路可以走，走第一条减1，走第二条减2，当走完后，就标记count++，完了就回溯，还有当走过了即出现负数了也要回溯，c代码如下 #include<stdio.h> int count=0; int a; void deep(int n) { if(a==n) count=0; if(n==0) { count++;return;//回溯} else if(n>0) { deep(n-1); deep(n-2); } else return;走过了也回溯 } int main() { int n; scanf("%d",&n); while(n--) { scanf("%d",&a); a=a-1;//只到第一级！！ deep(a); printf("%d\n",count); } } 本来可以了，可想到时间超限了！！！！最后想到是斐波那契数列，1+1=2,1+2=3,2+3=5........ 然后有下面代码 #include<stdio.h> int a[100]; int deep(int n) { int p; if(a[n]>0) return a[n]; if(n==1) return 1; if(n==2) return 1; if(n>2) a[n]=deep(n-1)+deep(n-2); return a[n]; } int main() { int n,sum,a; scanf("%d",&n); while(n--) { scanf("%d",&a); sum=deep(a); printf("%d\n",sum); } } 时间又超限了！！！！！ 也是，出现在递归函数里的式子经过递归后是一样的，也就是要再算，这就会多算了几道，所以时间超限， 我们可以再定义一个数组，里面都是0,当递归后存一遍算后的值，防止多算，只算一遍 #include<stdio.h> int a[100]; int deep(int n) { int p; if(a[n]>0) return a[n]; if(n==1) return 1; if(n==2) return 1; if(n>2) a[n]=deep(n-1)+deep(n-2); return a[n]; } int main() { int n,sum,a; scanf("%d",&n); while(n--) { scanf("%d",&a); sum=deep(a); printf("%d\n\n",sum); } }