「火」皇家烈焰

三维线性dp
dp[i][0/1][0/1]表示到了第i位，当前位和下一位是不是烈焰的状态。第二维表示当前位置，第三维表示下一个位置。
0表示不是，1表示是。
为什么不需要多开一个维度表示上一位？ 容易发现dp[i]的上一位就是dp[i-1]的当前位。所以不需要。

容易得到转移方程如下：

(上一位、当前位、下一位都是0)

（上一位是0，下一位是1或者上一位是1、下一位是0）

（上一位和下一位都是1）

(该位是1，上一位和下一位都不确定)

(该位、上一位、下一位都不确定)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll dp[1<<20][2][2];
char s[1<<20];
int main(){

    cin>>s+1;
    dp[0][0][0]=1;
    dp[0][0][1]=1;
    for(int i=1;s[i];i++){
        if(s[i]=='0'){
            dp[i][0][0]=dp[i-1][0][0]%mod;
        }
        if(s[i]=='1'){
            dp[i][0][1]=dp[i-1][0][0]%mod;
            dp[i][0][0]=dp[i-1][1][0]%mod;

        }
        if(s[i]=='2'){
            dp[i][0][1]=dp[i-1][1][0]%mod;
        }
        if(s[i]=='*'){
            dp[i][1][0]=(dp[i-1][1][1]+dp[i-1][0][1])%mod;
            dp[i][1][1]=dp[i][1][0];
        }
        if(s[i]=='?'){
            dp[i][1][0]=(dp[i-1][1][1]+dp[i-1][0][1])%mod;
            dp[i][1][1]=dp[i][1][0];

            dp[i][0][0]=(dp[i-1][1][0]+dp[i-1][0][0])%mod;
            dp[i][0][1]=dp[i][0][0];
        }
    }
    int n=strlen(s+1);
    cout<<(dp[n][1][0]+dp[n][0][0])%mod;
    return 0;
}