dp[i][1]:末尾為1的個數
dp[i][2]:末尾為2的個數
則：dp[i][1]=d[i-1][1]+dp[i-1][2]=dp[i-1]；dp[i][2]=dp[i-1][1]=dp[i-2][1]+dp[i-2][2]=dp[i-2]；
dp[i]=d[i-1]+dp[i-2]，
大數
[cpp]
include<stdio.h>
#include<string.h>
int dp[210][50],len[210];
int main()
{
int i,t,n,k,j;
char s[210];
dp[1][0]=1;len[1]=1;
dp[0][0]=1;len[0]=1;
for(i=2;i<210;i++)
{
k=0;
for(j=0;j<len[i-1];j++)
{
dp[i][j]=(dp[i-1][j]+dp[i-2][j]+k)%10;
k=(dp[i-1][j]+dp[i-2][j]+k)/10;
}
while(k>0)
{
dp[i][j++]=k%10;
k=k/10;
}
len[i]=j;
}
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
n=strlen(s);
//scanf("%d",&n);
for(j=len[n]-1;j>=0;j--)
printf("%d",dp[n][j]);
printf("\n");
}
return 0;
}
#include<stdio.h>
#include<string.h>
int dp[210][50],len[210];
int main()
{
int i,t,n,k,j;
char s[210];
dp[1][0]=1;len[1]=1;
dp[0][0]=1;len[0]=1;
for(i=2;i<210;i++)
{
k=0;
for(j=0;j<len[i-1];j++)
{
dp[i][j]=(dp[i-1][j]+dp[i-2][j]+k)%10;
k=(dp[i-1][j]+dp[i-2][j]+k)/10;
}
while(k>0)
{
dp[i][j++]=k%10;
k=k/10;
}
len[i]=j;
}
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
n=strlen(s);
//scanf("%d",&n);
for(j=len[n]-1;j>=0;j--)
printf("%d",dp[n][j]);
printf("\n");
}
return 0;
}
