$O(N)$ DP

动态规划

定义 dp[i] 表示前 i 个字符的解码方法总数。

状态转移考虑两种情况：

1. 单独解码最后一个字符：

   • 如果当前字符是 *，可以有 9 种解码方式（1-9）
   • 如果当前字符是 1-9，只有 1 种解码方式
   • 如果当前字符是 0，不能单独解码

2. 将最后两个字符一起解码：

   • 两个 *：可以组成 11-19、21-26，共 15 种方式
   • 第一个是 *，第二个是数字：
     • 数字 ≤ 6：* 可以是 1 或 2（2种）
     • 数字 > 6：* 只能是 1（1种）
   • 第一个是数字，第二个是 *：
     • 数字是 1：* 可以是 1-9（9种）
     • 数字是 2：* 可以是 1-6（6种）
   • 两个都是数字：组成 10-26 范围内的数字才能解码

#include <iostream>
#include <string>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    
    // dp[i]表示前i个字符的解码方法总数
    long long dp[n + 1];
    dp[0] = 1;  // 空字符串有1种解码方法
    
    // 处理第一个字符
    if (s[0] == '0') {
        dp[1] = 0;
    } else if (s[0] == '*') {
        dp[1] = 9;
    } else {
        dp[1] = 1;
    }
    
    // 填充dp数组
    for (int i = 2; i <= n; i++) {
        dp[i] = 0;
        
        // 情况1：将第i个字符单独解码
        if (s[i-1] == '*') {
            dp[i] = (dp[i] + dp[i-1] * 9) % MOD;
        } else if (s[i-1] != '0') {
            dp[i] = (dp[i] + dp[i-1]) % MOD;
        }
        
        // 情况2：将第i-1和i个字符一起解码
        if (s[i-2] == '*' && s[i-1] == '*') {
            // 两个*可以组成11-19, 21-26，共15种
            dp[i] = (dp[i] + dp[i-2] * 15) % MOD;
        } else if (s[i-2] == '*') {
            // 第一个是*，第二个是数字
            int num = s[i-1] - '0';
            if (num <= 6) {
                // *可以是1或2，共2种
                dp[i] = (dp[i] + dp[i-2] * 2) % MOD;
            } else {
                // *只能是1，共1种
                dp[i] = (dp[i] + dp[i-2]) % MOD;
            }
        } else if (s[i-1] == '*') {
            // 第一个是数字，第二个是*
            int num = s[i-2] - '0';
            if (num == 1) {
                // *可以是1-9，共9种
                dp[i] = (dp[i] + dp[i-2] * 9) % MOD;
            } else if (num == 2) {
                // *可以是1-6，共6种
                dp[i] = (dp[i] + dp[i-2] * 6) % MOD;
            }
        } else {
            // 两个都是数字
            int num = (s[i-2] - '0') * 10 + (s[i-1] - '0');
            if (num >= 10 && num <= 26) {
                dp[i] = (dp[i] + dp[i-2]) % MOD;
            }
        }
    }
    
    cout << dp[n] << endl;
    return 0;
}