404D Minesweeper 1D（记忆化搜寻，dp）

404D Minesweeper 1D（记忆化搜索，dp）

题目链接：http://codeforces.com/problemset/problem/404/D

题意：扫雷的游戏，给一串字符，'*'代表此处有地雷，'?'代表未知,'0'代表左右有0个,'1'代表左右有1个，'2'代表左右有2个；为给的字符串共有多少种合法的地雷分步情况；

解法：dp；ans[i][pre][now]表示i的位置之前一个位置地雷状态是pre（0/1），i位置地雷状态是now(0/1).在记忆化搜索的时候，只需排除非法，搜索合法的状态就可以；

代码：

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>

using namespace std;

#define eps 1e-8
typedef long long LL;
int inf=1000000007 ;

int ans[1000100][2][2];
char s[1000100];
int len;

int dfs(int add,int pre,int now)
{
    if(add==len)
        return now==0;
    if(ans[add][pre][now]!=-1) return ans[add][pre][now];
    if(now==1&&s[add]!='*'&&s[add]!='?') return 0;
    if(now==0&&s[add]=='*') return 0;
    int tool=0;
    for(int i=0;i<=1;i++)
    {
        int next=i;
         if(s[add]=='0'&&(pre+next)!=0) continue;
        if(s[add]=='1'&&(pre+next)!=1) continue;
        if(s[add]=='2'&&(pre+next)!=2) continue;
        tool+=dfs(add+1,now,next);tool%=inf;
    }
    return ans[add][pre][now]=tool;
}
int main()
{
  scanf("%s",s);
  len=strlen(s);
  memset(ans,-1,sizeof ans);
  cout<<(dfs(0,0,0)+dfs(0,0,1))%inf<<'\n';
   return 0;
}