題意:要求出一個長度為n的二進制數種不含相鄰1的個數，直接枚舉不現實2^45此方。。
解法:DP遞推，考慮長度為1時以0結尾和以1結尾的個數都為，長度為2時以0結尾的個數為長度為1時以0結尾的個數加上以1結尾的個數(因為在在0和1后面添加0任然滿足條 件),而長度為2時以1結尾的個數就等于長度為1時以0結尾的個數(因為不能出現兩個連續(xù)的1)。這樣給出了邊界條件和轉移方程，就可以遞推了。
簡化之后發(fā)現其實就一個斐波那切數列。
#include <stdio.h>
#define N 45
int a[N][2];
int main()
{
a[1][0] = a[1][1] = 1;
for(int i = 2; i < N; i++)
{
a[i][0] = a[i - 1][1] + a[i - 1][0];
a[i][1] = a[i - 1][0];
}
int t, n;
scanf("%d", &t);
for(int i = 1; i <= t; i++)
{
scanf("%d", &n);
printf("Scenario #%d:\n", i);
printf("%d\n\n", a[n][0] + a[n][1]);
}
return 0;
}