题意:要求出一个长度为n的二进制数种不含相邻1的个数，直接枚举不现实2^45此方。。
解法:DP递推，考虑长度为1时以0结尾和以1结尾的个数都为，长度为2时以0结尾的个数为长度为1时以0结尾的个数加上以1结尾的个数(因为在在0和1后面添加0任然满足条 件),而长度为2时以1结尾的个数就等于长度为1时以0结尾的个数(因为不能出现两个连续的1)。这样给出了边界条件和转移方程，就可以递推了。
简化之后发现其实就一个斐波那切数列。
#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;
}