Codefoeces 404 D Minesweeper 1 D「小範囲後効性」dp

タイトルリンク:http://codeforces.com/problemset/problem/404/D
标题:掃雷ゲームに似ていますが、行だけで、一部の格子は既知で、一部は未知で、'?'未知を表し、残りは既知である.'0'は左右に雷がないことを表し、'1'は左右に1つの雷があることを表し、'2'は左右に2つの雷があることを表し、'*'はそれ自体が雷であることを表す.合法的な状況は全部で何種類ありますか?(借りた題意)
ある状態が後の状態に影響される可能性があるように見えるが、後に影響を及ぼす状態は多くないため、この状態も現在のすべての状態に考慮して「後効性」を消す.

#include <iostream>   
#include <string>   
#include <cstring>   
#include <algorithm>   
#include <stdio.h>   
#include <cctype>   
#include <queue>   
#include <stdlib.h>   
#include <cstdlib>   
#include <math.h>   
#include <set>   
#include <vector>   
using namespace std; 
#define ll __int64
#define mod 1000000007

char s[3000005];
ll dp[1000005][5];
/*
0     0
1     1     
2     1     
3     2
4      

*/
int main(){
	ll i, j, k;
	while(~scanf("%s",s)){
		memset(dp[0], 0, sizeof(dp[0]));
		if(s[0]=='0')dp[0][0] = 1;
		else if(s[0]=='1')dp[0][2] = 1;
		else if(s[0]=='*')dp[0][4] = 1;
		else if(s[0]=='?')
			dp[0][0] = dp[0][2] = dp[0][4] = 1;

		for(i = 1; s[i]; i++){
			memset(dp[i], 0, sizeof(dp[i]));
			if(s[i] == '0'){
				dp[i][0] = dp[i-1][1] + dp[i-1][0];	dp[i][0] %= mod;
			}
			else if(s[i] == '1'){
				dp[i][1] = dp[i-1][4]; 
				dp[i][2] = dp[i-1][0] + dp[i-1][1];	dp[i][2] %= mod;
			}
			else if(s[i] == '2'){
				dp[i][3] = dp[i-1][4];
			}
			else if(s[i] == '*'){
				dp[i][4] = dp[i-1][2] + dp[i-1][3] + dp[i-1][4]; dp[i][4] %= mod;
			}
			else if(s[i] == '?'){
				dp[i][0] = dp[i-1][1] + dp[i-1][0];
				dp[i][1] = dp[i-1][4];
				dp[i][2] = dp[i-1][0] + dp[i-1][1];
				dp[i][3] = dp[i-1][4];
				dp[i][4] = dp[i-1][2] + dp[i-1][3] + dp[i-1][4];
				dp[i][0] %= mod; dp[i][4] %= mod; dp[i][2] %= mod;
			}
		}
		i--;
		ll ans = dp[i][0] + dp[i][1] + dp[i][4];
		printf("%I64d
", ans%mod);
	}
	return 0;
}