题意：

给定字符串，其中’*’表示地雷，’1’表示左/右边有一个地雷相邻，’2’表示左右两边均有地雷相邻，’0’表示左右均无地雷相邻，’?’表示待定，可填入0，1，2或者地雷，有多少种表示方法使字母串满足规定。

分析：

不难想到用dp[i][j]其中j为0,1,2,3（即四种状态），表示下标为i的元素为j状态时，前i+1个字符满足规定的种数。起初这样做，每次都还需要对前一个元素为’1’时进行特殊处理，要分两种情况，不如直接在dp数组中增加一个状态，表示起来也更清晰，即dp[i][j]中j可为0,1,2,3,4，其中0表示字符串下标为i的元素为0，1表示元素为1且前一个元素为地雷，2表示元素为1且前一个元素非地雷(0/1)，3表示元素为地雷，4表示元素为’2’。

代码：

#include<iostream>

#include<cstring>

using namespace std;

const int maxn = 1e6 + 5;

long long mod = 1000000007;

long long dp[maxn][5];

int main (void)

{

   string a;cin>>a;

    memset(dp,0,sizeof(dp));

    if(a[0]=='0') dp[0][0] = 1;

    else if(a[0] =='1') dp[0][2] = 1;

    else if(a[0] =='*') dp[0][3] = 1;

    else if(a[0]=='?') {

        dp[0][0] = 1;

        dp[0][3] = 1;

        dp[0][2] = 1;

    }

    for(int i = 1; i < a.length();i++){

        if(a[i]=='0') {

            dp[i][0] = (dp[i-1][1] + dp[i-1][0])%mod;

        }else if(a[i] == '1'){

            dp[i][1] = dp[i-1][3]%mod;

            dp[i][2] = (dp[i-1][1]+dp[i-1][0])%mod;

        }else if(a[i] == '*'){

            dp[i][3] = (dp[i-1][4]+dp[i-1][2]+dp[i-1][3])%mod;

        }else if(a[i] =='?'){

            dp[i][0] = (dp[i-1][1] + dp[i-1][0])%mod;

            dp[i][1] = dp[i-1][3]%mod;

            dp[i][2] = (dp[i-1][1]+dp[i-1][0])%mod;

            dp[i][3] = (dp[i-1][2]+dp[i-1][4]+dp[i-1][3])%mod;

            dp[i][4] =  dp[i-1][3]%mod;

        }else if(a[i] == '2'){

            dp[i][4] = dp[i-1][3]%mod;

        }

     //  for(int j= 0; j < 5; j++) cout<<dp[i][j]<<' ';

       //cout<<endl;

    }

    int len = a.length()-1;

    long long tot=(dp[len][0]+dp[len][1]+dp[len][3])%mod;

    cout<<tot<<endl;

}