超級樓梯

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);}}