BM69　把数字翻译成字符串¶

中等通过率 16.6%python3核心代码模式样例通过牛客 AC动态规划

牛客原题　源码

讲解章节：线性 DP

一句话

爬楼梯式计数 DP，末尾取 1 位还是 2 位决定能不能相加。

解题思路¶

这题考什么¶

骨架与跳台阶（BM63）完全一样，区别是每一步多了合法性判断：台阶随便跳，数字串却未必切得动。

状态定义：dp[i] = 前 i 个数字的译码方案数，dp[0] = 1（空串算一种译法）。按最后一个字母是由 1 位还是 2 位数字翻译来的分类，两类互不重叠：

dp[i] += dp[i-1]    当 s[i-1] != '0'                   末位单独成字母，对应 1..9
dp[i] += dp[i-2]    当 "10" <= s[i-2:i] <= "26"        末两位合成一个字母，对应 j..z

答案是 dp[n]。转移只回看两格，两个滚动变量即可，空间 O(1)。

全部难点集中在 '0' 上：

'0' 不能单独成字母（编码从 1 开始），只能被 "10" / "20" 吸收；
"30"、"07" 这类既不能单独也不能合成，dp[i] 就地变成 0，而 0 会顺着转移一路传下去，最终答案自然是 0，不需要额外的失败标记。

两位数还必须以 '1' 或 '2' 打头且不超过 26，"27" 不算。

数据规模与复杂度¶

0 < n <= 90，时限 2 秒（其他语言）。单趟扫描，时间 O(n)、空间 O(1)，比题面进阶要求的 O(n) 空间还省一档。 n = 90 且全是 '1' 时方案数达到 4660046610375530309（约 4.7e18），已经逼近 64 位有符号整数的上限 9.2e18；Python 的大整数不受这条限制，但用定长整型的语言必须选够宽的类型。

坑在哪¶

dp[0] = 1 不是 0。它表示「空串有一种译法」，是让 dp[2] 能取到「两位合成一个字母」这条路的支点；取 0 会把所有两位起手的方案整块抹掉。
首位是 '0' 时整串无解：代码把 b 初始化成 0，这个 0 随转移一路传导，最终返回 0，无须额外分支。
判两位合法要连着看两个字符：首位是 '1' 则第二位任意（10..19 全合法），首位是 '2' 则第二位必须 <= '6'。只判 int(s[i-2:i]) <= 26 会漏掉下界，把 "07" 误当成合法的 7。
末位是 '0' 时不能单独成字母，cur 要从 0 起算而不是从 b 起算；写成无条件的 cur = b 会把 "10" 数成 2 种。
返回的是 b（dp[n]）而不是 a（dp[n-1]）。n == 1 时循环不执行，初值 b 恰好就是答案。

样例复核¶

"12"：b 初值为 1（'1' 可单独成字母），i = 2 时末位 '2' 合法得 1，末两位 "12" 在 [10, 26] 内再加 a = 1，dp[2] = 2，与期望输出一致。

参考实现¶

solutions/nowcoder/BM69/sol.py
from typing import List, Optional


class Solution:
    def solve(self, nums: str) -> int:
        n = len(nums)
        if n == 0:
            return 0                                # 题面保证 n > 0；空串这里按 0 种译法处理
        # a = dp[i-2], b = dp[i-1]。dp[0] = 1 是「空串有一种译法」的约定，
        # 它让 i = 2 时的「两位合成」有值可加；首位为 '0' 时 dp[1] = 0，这个 0 会一路传导
        a, b = 1, 1 if nums[0] != "0" else 0
        for i in range(2, n + 1):
            cur = b if nums[i - 1] != "0" else 0    # 末位单独成字母：'0' 没有对应字母，贡献 0
            two = nums[i - 2]                       # 末两位合成一个字母，先看十位
            # 十位是 '1' 则个位任意（10..19）；十位是 '2' 则个位不能超过 '6'（20..26）
            if two == "1" or (two == "2" and nums[i - 1] <= "6"):
                cur += a
            a, b = b, cur                           # 两个变量同时挪位，右侧全用旧值
        return b                                    # b = dp[n]

BM69 把数字翻译成字符串¶