【每日一题】「火」皇家烈焰

问题：

解析：出处

三维dp， 表示当前第i位是否有火和后面一位是否有火。第二维取0表示当前位置没有火，取1表示有火，第三维取0表示当前位置没有火，取1表示有火。
这个三维dp的状态转移有点神奇，和之前转移的思想不太一样，这个是根据前一个状态和当前状态退出当前状态和下一个状态。
用字符数组整行输入。
1.

上一位、这一位、下一位取0。
2.


这一位取0下一位取1的方案数等于上一位取0这一位取0的方案数；这一位取0下一位取0的方案数等于上一位1取这一位取0的方案数，这一位是0，左右只有一个1。
3.

这一位取0下一位取1的方案数等于是上一位取1这一位取0的方案数，这一位取0，左右都是1。
4.

这一位是1，下一位不确定，对上一位没有要求，如果这一位不符合上一位的要求，方案数肯定就是0。
5.



相对 4 多了当前位不确定。
注意初始化 。不管第一个位置是1还是0的方案数都是1。
最后的结果取 ，因为最后一个位置可能0/1都可以取。（数据有点弱，最后的结果相加我忘记取模都过了）。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll dp[1000005][2][2];
char s[1000005];
int main() {
    int i; scanf("%s",s+1);
    dp[0][0][0]=dp[0][0][1]=1;
    for(i=1;s[i];++i) {
        if(s[i]=='0') {
            dp[i][0][0]=dp[i-1][0][0];
        }
        if(s[i]=='1') {
            dp[i][0][1]=dp[i-1][0][0];
            dp[i][0][0]=dp[i-1][1][0];
        }
        if(s[i]=='2') {
            dp[i][0][1]=dp[i-1][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];
        }
        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];
        }
    }
    printf("%lld\n",(dp[i-1][0][0]+dp[i-1][1][0])%mod);
}