题目描述
思路解析
一句话答案：LeetCode 91 解码方法像爬楼梯的计数动态规划：dp[i] 记前 i 位的方案数，末位非 '0' 就继承 dp[i-1]，末两位在 10~26 就加 dp[i-2]，两来路相加。'0' 最易翻车，时间 O(n)、空间 O(1)。
解码方法这道题到底在数什么
给一串数字 s，1 对 A、2 对 B、直到 26 对 Z。切成若干段、每段是 1~26 的数字，就还原一种字母串，问能解出多少种。226 可切成 2|2|6、22|6、2|26，答案是 3。要的是方案总数，不是某一种切法，是道计数题。
为什么不能把所有切法都试一遍
递归枚举切点：当前位既能单独成段，也能和前一位凑成两位段，一路分叉。每往前一位多一次二选一，切法随长度指数膨胀，串一长数不完，病根是同一个后缀（从某位到结尾的那截）被反复重算。换个记账法：只盯「前 i 位有几种方案」，算过存下来复用，指数枚举就压成线性递推（用前面算好的值一步步推出后面的）。
dp[i] 定成前 i 位的方案数，dp[0] 为什么是 1
定义 dp[i] 为「s 前 i 位的解码方案数」，i 数的是位数、不是字符下标。dp[0] = 1 代表空串——还没解出字母，算一种空方案；它不是真有字母，而是给「末两位合并」当基准：合并时前面剩的正好是空串，靠它记上一票。dp[1] 看首位，非 '0' 就能单独成字母，dp[1] = 1。
两条来路怎么相加，'0' 又卡在哪
算 dp[i] 时，落到第 i 位的最后一步有两种来路。一是末位单独成字母，前提是 s[i] 不是 '0'（没有字母配 0），成立就继承 dp[i-1]；二是末两位合并成字母，前提是这个两位数在 10~26，成立就加 dp[i-2]。两条末段长度不同，不会数重，相加即全部。
'0' 的坑全从这两个前提长出来。单独的 '0' 解不了，末位是 '0' 时第一条来路作废；两位数要不小于 10，'06' 带前导 0 不在 10~26，第二条也作废。某个 '0' 两条全断整串无解，比如 '30'：0 不能单独、30 又超 26。开头 '0' 同理，第一位无字母可对，返回 0。
拿 226122618 亲手把 dp 填一遍
空串 dp[0] = 1，'2' 非 0 得 dp[1] = 1。第 2 位 '2'：继承 1，末两位 22 在 10~26 加 1，dp[2] = 2。第 3 位 '6'：继承 2，26 加 1，dp[3] = 3。第 4 位 '1'：继承 3，61 超 26 作废，dp[4] = 3。第 5 位 '2'：继承 3，12 加 3，dp[5] = 6。第 6 位 '2'：继承 6，22 加 3，dp[6] = 9。第 7 位 '6'：继承 9，26 加 6，dp[7] = 15。第 8 位 '1'：继承 15，61 超 26 作废，dp[8] = 15。第 9 位 '8'：继承 15，18 加 15，dp[9] = 30，就是整串答案。
复杂度是多少，哪些 '0' 的边界最坑
从第 2 位推到第 n 位，每位只做常数次判断，时间 O(n)；dp[i] 只依赖 dp[i-1] 和 dp[i-2]，两个变量轮替就够，不必存整张表，空间 O(1)。参考代码的 a、b 就是这两项。
另两个易错点：两位数要卡死 10~26 两头，'09' 小于 10 非法、'27' 大于 26 只能拆开；别把 dp[0] 当真有字母，它只是空串那一票基准。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
枚举全部分组会重复计算相同前缀。动态规划保存每个前缀的方案数，再按末尾长度分类相加。
上行是字符串 s 的每一位（固定不动），下行 dp 待填。第 0 列代表「空串」，从最左边开始。
dp[0]=1 表示空前缀有一种分组方式。例如整个前缀为 "22" 时，取末两位需要这一个起始方案。
只看第 1 位 '2'：它是 1~9 的数字，能单独解成一个字母，所以 dp[1]=1。
计算前 2 位：末位 2 可单独解码，贡献 1 种；末两位 22 可解码，贡献 1 种。
末尾取一位有 1 种，取两位有 1 种，合计 2 种，写入 dp[2]。
计算前 3 位：末位 6 可单独解码，贡献 2 种；末两位 26 可解码，贡献 1 种。
末尾取一位有 2 种，取两位有 1 种，合计 3 种，写入 dp[3]。
计算前 4 位：末位 1 可单独解码，贡献 3 种；末两位 61 大于 26，不计入。
末尾取一位有 3 种，取两位有 0 种，合计 3 种，写入 dp[4]。
计算前 5 位：末位 2 可单独解码，贡献 3 种；末两位 12 可解码，贡献 3 种。
末尾取一位有 3 种，取两位有 3 种，合计 6 种，写入 dp[5]。
计算前 6 位：末位 2 可单独解码，贡献 6 种；末两位 22 可解码，贡献 3 种。
末尾取一位有 6 种，取两位有 3 种，合计 9 种，写入 dp[6]。
计算前 7 位：末位 6 可单独解码，贡献 9 种；末两位 26 可解码，贡献 6 种。
末尾取一位有 9 种，取两位有 6 种，合计 15 种，写入 dp[7]。
计算前 8 位：末位 1 可单独解码，贡献 15 种；末两位 61 大于 26，不计入。
末尾取一位有 15 种，取两位有 0 种，合计 15 种，写入 dp[8]。
计算前 9 位：末位 8 可单独解码，贡献 15 种；末两位 18 可解码，贡献 15 种。
末尾取一位有 15 种，取两位有 15 种，合计 30 种，写入 dp[9]。
最右 dp[9]=30 就是整串 "226122618" 的解码方案总数。
含 0 的例子：s="10"。空前缀的方案数为 1。
前 1 位：末位 "1" 贡献 1 种，合计 1 种。
前 2 位：末位 "0" 贡献 0 种，末两位 "10" 贡献 1 种，合计 1 种。
含 0 的例子：s="30"。空前缀的方案数为 1。
前 1 位：末位 "3" 贡献 1 种，合计 1 种。
前 2 位：末位 "0" 贡献 0 种，末两位 "30" 贡献 0 种，合计 0 种。
含 0 的例子：s="101"。空前缀的方案数为 1。
前 1 位：末位 "1" 贡献 1 种，合计 1 种。
前 2 位：末位 "0" 贡献 0 种，末两位 "10" 贡献 1 种，合计 1 种。
前 3 位：末位 "1" 贡献 1 种，末两位 "01" 贡献 0 种，合计 1 种。
检查字符 0 所在的位置与相邻字符。出现 0 不一定无解，例如 10 可以解成 J。
滚动状态减少存储，但不能省掉字符合法性判断。
参考代码
class Solution: def numDecodings(self, s: str) -> int: if not s or s[0] == "0": return 0 a, b = 1, 1 # 循环处理 s[i] 前：a=dp[i-1]，b=dp[i] for i in range(1, len(s)): cur = b if s[i] != "0" else 0 if 10 <= int(s[i-1:i+1]) <= 26: cur += a a, b = b, cur return b复杂度
- 时间：O(n)，n 为字符串长度，每位检查单字符与两字符两种情况
- 空间：O(1)，滚动只留前两项 a、b
易错点
面试追问把动画讲成自己的话
追问为什么能滚动数组优化？
追问和爬楼梯 LC70 的关系？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
零钱兑换
LeetCode 322 · 中等 · 沿着 一维动态规划 继续往下推进