数位 DP：统计区间数字规律

解码方法（LeetCode 91）

数字字符串 s，解码方式数（1→A，2→B…26→Z）：

public int numDecodings(String s) {
    int n = s.length();
    int[] dp = new int[n+1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == '0' ? 0 : 1;
    for (int i = 2; i <= n; i++) {
        int one = Integer.parseInt(s.substring(i-1, i));
        int two = Integer.parseInt(s.substring(i-2, i));
        if (one >= 1) dp[i] += dp[i-1];         // 单独解码
        if (two >= 10 && two <= 26) dp[i] += dp[i-2]; // 两位解码
    }
    return dp[n];
}

解码方法 II（LeetCode 639）

含 * 号（代表 1-9），解码方式数（结果模 1e9+7）：

public int numDecodings(String s) {
    int n = s.length();
    long MOD = 1_000_000_007;
    long[] dp = new long[n+1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == '*' ? 9 : (s.charAt(0) == '0' ? 0 : 1);
    for (int i = 2; i <= n; i++) {
        char cur = s.charAt(i-1), prev = s.charAt(i-2);
        // 单独解码 s[i-1]
        if (cur == '*') dp[i] += 9 * dp[i-1];
        else if (cur != '0') dp[i] += dp[i-1];
        // 两位解码 s[i-2..i-1]
        if (prev == '*' && cur == '*') dp[i] += 15 * dp[i-2]; // 11-19,21-26
        else if (prev == '*') dp[i] += (cur <= '6' ? 2 : 1) * dp[i-2];
        else if (cur == '*') {
            int p = prev - '0';
            if (p == 1) dp[i] += 9 * dp[i-2];
            else if (p == 2) dp[i] += 6 * dp[i-2];
        } else {
            int two = Integer.parseInt("" + prev + cur);
            if (two >= 10 && two <= 26) dp[i] += dp[i-2];
        }
        dp[i] %= MOD;
    }
    return (int) dp[n];
}

不同子序列（LeetCode 115）

s 中通过删除字符得到 t 的方式数，dp[i][j] = s[0..i-1] 中 t[0..j-1] 的子序列数：

public int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    long[][] dp = new long[m+1][n+1];
    for (int i = 0; i <= m; i++) dp[i][0] = 1; // 空 t 有 1 种方式（删完）
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i-1][j]; // 不使用 s[i-1]
            if (s.charAt(i-1) == t.charAt(j-1))
                dp[i][j] += dp[i-1][j-1]; // 使用 s[i-1] 匹配 t[j-1]
        }
    }
    return (int) dp[m][n];
}

总结