记录后两位,共有4种情况
00->0
01->1
10->2
11->3;
dp[i][0]=dp[i-1][0]+dp[i-1][2];
dp[i][1]=dp[i-1][0];
dp[i][2]=dp[i-1][1]+dp[i-1][3];
dp[i][3]=dp[i-1][1]+dp[i-1][3];
#include<stdio.h> #include<string.h> #include<stdlib.h> #define inf 9997 int dp[10001][4]; int main() { int i,j,n,k,max; memset(dp,0,sizeof(dp)); dp[1][0]=2; dp[2][0]=1; dp[2][1]=1; dp[2][2]=1; dp[2][3]=1; for(i=3;i<10000;i++) { dp[i][0]=(dp[i-1][0]+dp[i-1][2])%inf; dp[i][1]=(dp[i-1][0])%inf; dp[i][2]=(dp[i-1][1]+dp[i-1][3])%inf; dp[i][3]=(dp[i-1][1]+dp[i-1][3])%inf; } while(scanf("%d",&n),n>=0) { int sum=0; for(i=0;i<4;i++) sum=(sum+dp[n][i])%inf; printf("%d\n",sum); } return 0; }