【每日一题】「火」皇家烈焰 (dp / 递推)

Solution
题意:

0：这个格子没有烈焰，且其左右两个格子均没有烈焰

1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰

2：这个格子没有烈焰，且其左右两个格子中均有烈焰

*：这个格子有烈焰

？：未告诉你本格情况

求满足条件的方案数。

思路：

考虑用 表示第 i 个字符 是/不是 火焰 以及 下一位是/不是 火焰的情况。
因为前一位是 所以可以递推，然后只考虑下一位的情况。

eg:
初始化：

结果,因为最后一位可以是1也可以是0：

,前一位肯定不是火焰:

,前一位是火焰下一位不是和 前一位不是下一位是：

,前一位肯定是火焰:
,两种情况都要考虑：

,所有情况都要考虑：

Code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int mo=998244353; const int mod=1000000007;

const int manx=1e6+5;
const int N=1e3+5;

ll dp[manx][2][2];
string s;
//  ll a[N][N];

int main(){
    io;
    cin>>s; s=" "+s;
    ll n=s.size();
    dp[0][0][1]=dp[0][0][0]=1;
    for(int i=1;i<=n;i++){
        if(s[i]=='0') dp[i][0][0]=dp[i-1][0][0]%mod;
        else if(s[i]=='1'){
            dp[i][0][0]=dp[i-1][1][0]%mod;
            dp[i][0][1]=dp[i-1][0][0]%mod;
        }
        else if(s[i]=='2') dp[i][0][1]=dp[i-1][1][0]%mod;
        else if(s[i]=='*'){
            dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])%mod;
            dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])%mod;
        }
        else if(s[i]=='?'){
            dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])%mod;
            dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])%mod;

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