学步园

题目链接：Click here~~

题意：

一种只有0、1两种元素的串，问长度为 i 的串中包含多少个不含有“101”的串。

解题思路：

令 dp[i] 表示长度为 i 的串满足要求的串的个数。

很容易想到 dp[i] = 2*dp[i-1] - { dp[i-1] 中末尾两位是"10"的串的个数 }。

而 { } 中的内容又可以表示成 dp[i-1] 中末位是“0”的串的个数 - dp[i-2] 中末位是“0”的串的个数。

又因为 dp[j] 中末位是“0”的个数等于 dp[j-1] 。

于是得到状态转移方程：dp[i] = 2*dp[i-1] - (dp[i-2] - dp[i-3])。

#include <stdio.h>
int main()
{
    int dp[10001]={0,2,4,7};
    for(int i=4;i<10000;i++)
        dp[i] = (2*dp[i-1]-dp[i-2]+dp[i-3])%9997;
    int n;
    while(scanf("%d",&n),n+1)
        printf("%d\n",dp[n]);
    return 0;
}