AI019. 标注序列还原计数

解题思路

这道题在考什么

序列生成型 DP 的经典骨架:逐位扫描,每一位问「我能接在谁后面」。转移长得和爬楼梯一模一样(dp[i] = dp[i-1] + dp[i-2]),难点全在合法性条件——0 和 27~30 这些非法编号把两条转移各挂了一道闸。

状态与转移(DP 三问)

dp[i] = 前 i 个字符能还原的方案数。第 i 个字符有两种来路:

• 自己单独成一个编号:要求 s[i] 在 '1'~'9'(0 不能单独成编号)→ 贡献 dp[i-1]。
• 和前一个字符组成两位编号:要求 s[i-1]s[i] 在 "10"~"26" → 贡献 dp[i-2]。

两条闸都关上时 dp[i] = 0——比如 "30",3 后面跟 0,0 既不能单独成编号,30 又超出 26,整串无解。初始值 dp[0] = 1(空串一种方案),首字符为 '0' 直接输出 0。

取模的纪律

|s| 可达 10 万,方案数按斐波那契速度增长,必须对 1e9+7 取模。一个隐蔽的坑:别用「中途 dp 值为 0 就提前退出」当优化——取模后的 0 不代表真实方案数为 0(理论上可能撞上模数的倍数),正确的无解判断只能来自转移条件本身。参考解从头到尾老实转移,不做这种「聪明」优化。

滚动变量

转移只看前两格,两个变量滚动即可,空间 O(1):

prev2, prev1 = 1, (首字符合法 ? 1 : 0)
每一位:cur = (单走贡献 + 两位贡献) % MOD

数据范围读档

O(n) 一遍扫,10 万长度毫无压力。这道题没有部分分空间——要么转移条件写对全过,要么在 0 的三种位置(开头/中间可救/中间无解)上批量挂,建议把 "10"、"100"、"1002" 手算一遍再提交(1、0、2 分别怎么接)。

易错点展开

• '0' 单独成编号:0 只能作为 10、20 的个位存在。
• 27、28、29 当成合法两位数:上限是 26。
• 首字符 '0' 没特判。
• 忘取模或只在最后取模:中间值溢出(Python 不溢出但慢,C++/Java 直接错)。

参考实现怎么读

参考实现两个滚动变量 prev2、prev1,每一位算 cur:s[i] 在 '1'-'9' 时加 prev1,s[i-1:i+1] 在 "10"-"26" 时加 prev2,取模后滚动。两位数判断用整数比较 10 <= int(s[i-1:i+1]) <= 26,比字符逐位比对不容易漏 27~30。

写完先自查这四串

1. "10":1 可单走,10 可两位;但 0 不能单走,所以只有「10」一种,答案 1。 2. "100":第二个 0 前面是 0,既不能单走也组不成 10-26(00 非法),答案 0。 3. "226":2-2-6、22-6、2-26 共 3 种,对齐样例。 4. "1111111111"(十个 1):答案是斐波那契第 11 项 89,验证转移骨架和爬楼梯确实同源。

数据范围与语言细节

O(n) 扫 10 万字符,瓶颈不在算法。C++/Java 记得每步取模,乘法不出现所以不会溢出 long,但加法不取模累积几万步也会超 int;Python 无溢出,照样取模保持输出正确。