简单dp ---HDU3485 Count 101

题目大意：让求长度为n的0 和 1 构成的串中不包含101子串的个数有多少。

这个题当时想了好久，以为是一个规律题，一直在推规律，最后还是wa了，上网一看原来是dp问题， 不过确实递推式挺巧妙的。

递推式dp[i] = 2 * dp[i - 1] - dp[i - 2] + dp[i - 3];

现在就来推一下这个式子，首先dp[i]就表示当长度为 i 的 的时候满足条件(就是串中不含101)的个数，dp[i] = 2 * dp[i - 1] - {最后两位是10的个数}，其中2 * dp[i-1]就表示总数，最后两位是10的个数就等于 最后一位是0的个数减去倒数第二位是0的个数， 还有一个问题就是最后一位是0怎么求， 最后一个是零的个数就是dp[i-1]， 因为当前位的总个数等于前一位乘2， 因为是只有0和1两种状态，所以是0的个数就是前一位的数所以 {最后两位是10的个数} = dp[i - 2] - dp[i - 3]; 所以这个式子最后就是dp[i] = 2 * dp[i - 1] - dp[i - 2] + dp[i - 3];

代码如下：

1 #include<iostream>
 2 #include <stdio.h>
 3 using namespace std;
 4 int dp[10010];
 5 int main()
 6 {
 7     dp[0] = 0; dp[1] = 2; dp[2] = 4; dp[3] = 7;
 8     for (int i = 4; i < 10010; i++)
 9         dp[i] = (2 * dp[i - 1] -  dp[i - 2] +  dp[i - 3]) % 9997 ;
10     int n;
11     while (~scanf("%d", &n) && n != -1)
12     {
13         printf("%d
", dp[n]);
14     }
15     return 0;
16 }

1 #include 2 #include 3 using namespace std; 4 int dp[10010]; 5 int main() 6 { 7 dp[0] = 0; dp[1] = 2; dp[2] = 4; dp[3] = 7; 8 for (int i = 4; i < 10010; i++) 9 dp[i] = (2 * dp[i - 1] - dp[i - 2] + dp[i - 3]) % 9997 ; 10 int n; 11 while (~scanf("%d", &n) && n != -1) 12 { 13 printf("%d ", dp[n]); 14 } 15 return 0; 16 }

题目大意：让求长度为n的0 和 1 构成的串中不包含101子串的个数有多少。 这个题当时想了好久，以为是一个规律题，一直在推规律，最后还是wa了，上网一看原来是dp问题， 不过确实递推式挺巧妙的。 递推式dp[i] = 2 * dp[i - 1] - dp[i - 2] + dp[i - 3]; 现在就来推一下这个式子，首先dp[i]就表示当长度为 i 的 的时候满足条件(就是串中不含101)的个数，dp[i] = 2 * dp[i - 1] - {最后两位是10的个数}，其中2 * dp[i-1]就表示总数，最后两位是10的个数就等于 最后一位是0的个数减去倒数第二位是0的个数， 还有一个问题就是最后一位是0怎么求， 最后一个是零的个数就是dp[i-1]， 因为当前位的总个数等于前一位乘2， 因为是只有0和1两种状态，所以是0的个数就是前一位的数所以 {最后两位是10的个数} = dp[i - 2] - dp[i - 3]; 所以这个式子最后就是dp[i] = 2 * dp[i - 1] - dp[i - 2] + dp[i - 3]; 代码如下： 1 #include 2 #include 3 using namespace std; 4 int dp[10010]; 5 int main() 6 { 7 dp[0] = 0; dp[1] = 2; dp[2] = 4; dp[3] = 7; 8 for (int i = 4; i < 10010; i++) 9 dp[i] = (2 * dp[i - 1] - dp[i - 2] + dp[i - 3]) % 9997 ; 10 int n; 11 while (~scanf("%d", &n) && n != -1) 12 { 13 printf("%d ", dp[n]); 14 } 15 return 0; 16 }