超级楼梯

223 Sample Output
12 Authorlcy Source2005实验班短学期考试 Recommendlcy开始我是用回溯法，把这个问题抽象成完全二叉树，每次有两条路可以走，走第一条减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;//回溯}elseif(n>0){deep(n-1);deep(n-2);}elsereturn;走过了也回溯}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);}}