超級(jí)樓梯

223 Sample Output
12 Authorlcy Source2005實(shí)驗(yàn)班短學(xué)期考試 Recommendlcy開始我是用回溯法，把這個(gè)問題抽象成完全二叉樹，每次有兩條路可以走，走第一條減1，走第二條減2，當(dāng)走完后，就標(biāo)記count++，完了就回溯，還有當(dāng)走過了即出現(xiàn)負(fù)數(shù)了也要回溯，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;//只到第一級(jí)！！deep(a);printf("%d/n",count);}}本來可以了，可想到時(shí)間超限了！！！！最后想到是斐波那契數(shù)列，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);}}時(shí)間又超限了！！！！！也是，出現(xiàn)在遞歸函數(shù)里的式子經(jīng)過遞歸后是一樣的，也就是要再算，這就會(huì)多算了幾道，所以時(shí)間超限，我們可以再定義一個(gè)數(shù)組，里面都是0,當(dāng)遞歸后存一遍算后的值，防止多算，只算一遍#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);}}