題意:要求出一個長度為n的二進制數(shù)種不含相鄰1的個數(shù)，直接枚舉不現(xiàn)實2^45此方。。
解法:DP遞推，考慮長度為1時以0結(jié)尾和以1結(jié)尾的個數(shù)都為，長度為2時以0結(jié)尾的個數(shù)為長度為1時以0結(jié)尾的個數(shù)加上以1結(jié)尾的個數(shù)(因為在在0和1后面添加0任然滿足條 件),而長度為2時以1結(jié)尾的個數(shù)就等于長度為1時以0結(jié)尾的個數(shù)(因為不能出現(xiàn)兩個連續(xù)的1)。這樣給出了邊界條件和轉(zhuǎn)移方程，就可以遞推了。
簡化之后發(fā)現(xiàn)其實就一個斐波那切數(shù)列。
#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;
}