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