典型的DP打表輸出水題。。。不過用遞歸卻會超時，ORZ

對于這樣一個0,1序列,a1,a2,a3,...a(i-2),a(i-1),a(i)...
設f(i)為輸入的數對應的結果
用DP做的話,假設f(i-2),f(i-1)已經知道了,那么求f(i)應該如下:
當取a(i)=0,那么結果肯定和f(i-1)是一樣的,因為在后面追加的是0,肯定不會導致存在相鄰;
當取a(i)=1,那么此時只要知道a(i-2)就可以了,因為我們可以使a(i-1)為0,這樣就不會導致相鄰的1了;
所以a[i]=a[i-1]+a[i-2];

#include <iostream>
#include <string>
using namespace std;

int fabi[50];
void init()
{
    fabi[1]=2;
    fabi[2]=3;
    for (int j=3;j<=45;j++)
    {
        fabi[j]=fabi[j-1]+fabi[j-2];
    }
}

int main()
{
     int n,i=1,num;
     init();
     cin>>n;
     while (n>0)
     {
         cin>>num;
         printf("Scenario #%d:\n",i++);
         printf("%d\n\n",fabi[num]);
         n--;
     }
}