解码方法如何用动态规划求解？如何处理 0 和两位数边界？

简化版

解码方法用 dp[i] 表示前 i 个字符的解码方案数。若第 i 个字符不是 0，可以单独解码，贡献 dp[i-1]；若最后两位组成 10..26，可以合并解码，贡献 dp[i-2]。

详细版

核心转移是看当前位置能否由“一位字符”或“两位字符”结尾。设字符串下标从 0 开始，dp[i] 表示 s[0..i-1] 的方案数，初始化 dp[0]=1。遍历 i=1..n 时，若 s[i-1] 在 '1'..'9'，说明最后一位可以单独解码，dp[i] += dp[i-1]；若 i>=2 且 s[i-2..i-1] 在 10..26，说明最后两位可以合并解码，dp[i] += dp[i-2]。

0 不能单独解码，只能作为 10 或 20 的一部分。因此 "06"、"30" 都是 0 种方案。空间可以从数组优化成两个变量，因为转移只依赖前一项和前两项。

完整版教学

一、为什么这是动态规划题

字符串 "226" 可以解码为：

2 | 2 | 6 -> B B F
22 | 6    -> V F
2 | 26    -> B Z

每一种完整解码都可以看作前缀解码后接上一段合法编码。当前位置的答案依赖前一个前缀和前两个前缀，这就是典型的重叠子问题。

dp[i]：前 i 个字符有多少种解码方式
最后一步：单独使用第 i 个字符，或合并使用第 i-1、i 个字符

二、状态定义为什么用前 i 个字符

用 dp[i] 表示 s[0..i-1] 的方案数，比用字符下标更清楚，因为空前缀可以自然写成 dp[0] = 1。

状态	含义
`dp[0]`	空字符串，作为拼接基础有 1 种方式
`dp[1]`	前 1 个字符的解码方式
`dp[i]`	前 i 个字符的解码方式

dp[0]=1 不是说空串真的有一种字母翻译，而是为了当 "10"、"26" 这种两位整体合法时，可以贡献 dp[0]。

记忆钩子：计数 DP 里的空状态常常是“拼接单位元”，不是实际答案。

三、一位字符什么时候能贡献

如果 s[i-1] 是 '1'..'9'，它可以单独映射到 A..I，那么所有前 i-1 个字符的方案后面都能接上它。

s = "226", i = 3
最后一位 "6" 合法
dp[3] += dp[2]

如果当前字符是 '0'，它不能单独映射，所以不能加 dp[i-1]。这是本题最容易漏掉的边界。

四、两位字符什么时候能贡献

如果最后两位组成的数字在 10..26，它们可以合并成一个字母，于是所有前 i-2 个字符的方案后面都能接上这两位。

s = "226", i = 3
最后两位 "26" 合法
dp[3] += dp[1]

判断时不要只看数字小于等于 26，还要保证十位不是 0。"06" 解析成整数是 6，但不能按 "06" 映射成 F。

五、用样例完整推一遍

以 "226" 为例：

i	前缀	一位贡献	两位贡献	dp[i]
0	空	-	-	1
1	2	`dp[0]`	-	1
2	22	`dp[1]`	`dp[0]`	2
3	226	`dp[2]`	`dp[1]`	3

所以答案是 3。

六、代码模板和空间压缩

int numDecodings(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        char one = s.charAt(i - 1);
        if (one >= '1' && one <= '9') {
            dp[i] += dp[i - 1];
        }
        if (i >= 2) {
            int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
            if (two >= 10 && two <= 26) {
                dp[i] += dp[i - 2];
            }
        }
    }
    return dp[n];
}

因为只依赖 dp[i-1] 和 dp[i-2]，可用两个变量压缩空间，但面试优先写数组版更不容易错。

七、常见误区与追问

误区：把 0 当作普通数字。 0 不能单独解码，只能出现在 10 或 20 中。
误区：用 Integer.parseInt("06") 后认为合法。 两位编码不能以 0 开头，06 不在合法编码范围。
误区：初始化 dp[0]=0。 这样 "10" 的两位贡献会被错误算成 0。
追问：为什么是加法转移？ 最后一位单独解和最后两位合并解是互斥方案集合，计数要相加。
追问：空间如何优化？ 只保留前一项和前两项即可，时间仍是 O(n)。
追问：空字符串返回多少？ LeetCode 输入通常非空；若业务语义要求空串不可解，可在入口单独返回 0。

八、加强记忆

解码方法可以记成“最后一步分类计数”：每个前缀的方案只来自两种结尾，一位合法就接 dp[i-1]，两位在 10..26 就接 dp[i-2]。所有坑都围绕 0 展开：0 不能单独用，06 不能当 6，用 dp[0]=1 是为了让两位整体解码有基础。面试时先讲状态定义，再讲两条贡献条件，最后用 "226" 和 "06" 做正反例，答案会很稳。

简化版

详细版