hdu 1865

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;
}