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

對于這樣一個0,1序列,a1,a2,a3,...a(i-2),a(i-1),a(i)...
設(shè)f(i)為輸入的數(shù)對應(yīng)的結(jié)果
用DP做的話,假設(shè)f(i-2),f(i-1)已經(jīng)知道了,那么求f(i)應(yīng)該如下:
當(dāng)取a(i)=0,那么結(jié)果肯定和f(i-1)是一樣的,因為在后面追加的是0,肯定不會導(dǎo)致存在相鄰;
當(dāng)取a(i)=1,那么此時只要知道a(i-2)就可以了,因為我們可以使a(i-1)為0,這樣就不會導(dǎo)致相鄰的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--;
     }
}