京公网安备11010502063487号把 A 到 Z 分别编码成 1 到 26，给定一个只含数字的字符串，问一共有多少种方式把它解码回字母序列。同一个字符串可能有多种拆法："226" 可以拆成 2, 2, 6（BBF）、22, 6（VF）、2, 26（BZ）三种。字符 0 是麻烦的来源：它不能单独解码，只能和前面的 1 或 2 组成 10、20。动态规划：dp[i] 表示前 i 个字符的解码方式数，dp[i] 由两部分相加：如果最后一个字符不是 0，可以单独解码，加上 dp[i-1]；如果最后两个字符组成的数在 10 到 26 之间，可以合起来解码，加上 dp[i-2]。本文用真实数据展示不处理 0 的错误，展示不带记忆化的递归调用次数（正好是斐波那契增长），给出五种语言的实现，并把填表做成分步演示。
完整题目见官方页面（链接在文末）。字符串可能以 0 开头（这时答案是 0）。基准解是自顶向下的记忆化递归：go(i) 表示从位置 i 开始的解码方式数，从前往后处理，与从前往后填 dp 表的方向不同。一共 16 组用例，覆盖：官方三个示例、以 0 开头、含 10、20、100 这样的 0、两位数超过 26（27、30）、全是 1（斐波那契）、较长的混合串：
输入 ["12"] 输出 2 输入 ["226"] 输出 3 输入 ["06"] 输出 0 输入 ["0"] 输出 0 输入 ["10"] 输出 1 输入 ["1"] 输出 1
0 不能单独解码。如果不判断最后一个字符是不是 0，就会把它当成一个合法的单字符；如果对"最后两位"只看数值是否不超过 26，就会把 06、00 当成合法。下面是把 0 当作普通字符的写法（单独解码时不检查是否为 0）与 solve 的真实结果：
# 没有处理 0 的写法（0 本身不能单独解码；只有 10、20 能用 0 结尾） '12': 该写法 -> 2 solve -> 2 '226': 该写法 -> 3 solve -> 3 '06': 该写法 -> 1 solve -> 0 '10': 该写法 -> 2 solve -> 1 '100': 该写法 -> 2 solve -> 0 '30': 该写法 -> 1 solve -> 0 '2101': 该写法 -> 3 solve -> 1 随机 20000 组：该写法与正确答案不同的有 12356 组（61.8%）
"06" 应该是 0（以 0 开头无法解码），错误写法给出 1；"10" 只能解成 J（一种），错误写法给出 2（多算了把 1、0 分开的那种）；"100" 应该是 0（最后一个 0 前面是 0，00 不合法），错误写法给出 2；"2101" 应该是 1，错误写法给出 3。"12" 和 "226" 里没有 0，两种写法一致。在随机的 20000 组数据里（数字偏向 0、1、2、6），这种写法出错的有 12356 组，占 61.8%。
先处理字符串以 0 开头的情形，直接返回 0。用两个变量滚动：prev2 是 dp[i-2]，prev1 是 dp[i-1]，初始都是 1（空串和第一个字符各有 1 种）。对 i 从 1 开始：cur 先记为 0；如果 s[i] 不是 0，cur += prev1；如果 s[i-1] 不是 0 并且 s[i-1]s[i] 组成的两位数不超过 26，cur += prev2；然后滚动 prev2 = prev1、prev1 = cur。最后返回 prev1。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(s): prev2, prev1 = 1, 1 # prev2 = dp[i-2]，prev1 = dp[i-1]；dp[0] = 1（空串有 1 种解码），前一个位置尚未开始时也记 1 if s[0] == "0": return 0 for i in range(1, len(s)): cur = 0 if s[i] != "0": # 单独解码 s[i]：不能是 0 cur += prev1 if s[i - 1] != "0" and 10 <= int(s[i - 1:i + 1]) <= 26: # 与前一位合起来解码：两位数在 10 到 26 之间 cur += prev2 prev2, prev1 = prev1, cur return prev1
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON ["12"] → 2 ["226"] → 3 ["06"] → 0 ["0"] → 0 ["10"] → 1 ["1"] → 1
Java · 解法代码class Solution { public int numDecodings(String s) { if (s.charAt(0) == '0') return 0; int prev2 = 1, prev1 = 1; // prev2 = dp[i-2]，prev1 = dp[i-1] for (int i = 1; i < s.length(); i++) { int cur = 0; if (s.charAt(i) != '0') cur += prev1; // 单独解码 s[i]：不能是 0 int two = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0'); if (s.charAt(i - 1) != '0' && two <= 26) cur += prev2; // 与前一位合起来解码：两位数在 10 到 26 之间 prev2 = prev1; prev1 = cur; } return prev1; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl ["12"] → 2 ["226"] → 3 ["06"] → 0 ["0"] → 0 ["10"] → 1 ["1"] → 1
Go · 解法代码func numDecodings(s string) int { if s[0] == '0' { return 0 } prev2, prev1 := 1, 1 // prev2 = dp[i-2]，prev1 = dp[i-1] for i := 1; i < len(s); i++ { cur := 0 if s[i] != '0' { // 单独解码 s[i]：不能是 0 cur += prev1 } two := int(s[i-1]-'0')*10 + int(s[i]-'0') if s[i-1] != '0' && two <= 26 { // 与前一位合起来解码：两位数在 10 到 26 之间 cur += prev2 } prev2, prev1 = prev1, cur } return prev1 }
$ go build -o bin . && ./bin < cases.jsonl ["12"] → 2 ["226"] → 3 ["06"] → 0 ["0"] → 0 ["10"] → 1 ["1"] → 1
JavaScript · 解法代码function numDecodings(s) { if (s[0] === "0") return 0; let prev2 = 1, prev1 = 1; // prev2 = dp[i-2]，prev1 = dp[i-1] for (let i = 1; i < s.length; i++) { let cur = 0; if (s[i] !== "0") cur += prev1; // 单独解码 s[i]：不能是 0 const two = Number(s[i - 1]) * 10 + Number(s[i]); if (s[i - 1] !== "0" && two <= 26) cur += prev2; // 与前一位合起来解码：两位数在 10 到 26 之间 prev2 = prev1; prev1 = cur; } return prev1; }
$ node run.js < cases.jsonl ["12"] → 2 ["226"] → 3 ["06"] → 0 ["0"] → 0 ["10"] → 1 ["1"] → 1
C++ · 解法代码#include <string> using namespace std; class Solution { public: int numDecodings(string s) { if (s[0] == '0') return 0; int prev2 = 1, prev1 = 1; // prev2 = dp[i-2]，prev1 = dp[i-1] for (size_t i = 1; i < s.size(); i++) { int cur = 0; if (s[i] != '0') cur += prev1; // 单独解码 s[i]：不能是 0 int two = (s[i - 1] - '0') * 10 + (s[i] - '0'); if (s[i - 1] != '0' && two <= 26) cur += prev2; // 与前一位合起来解码：两位数在 10 到 26 之间 prev2 = prev1; prev1 = cur; } return prev1; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl ["12"] → 2 ["226"] → 3 ["06"] → 0 ["0"] → 0 ["10"] → 1 ["1"] → 1
共 16 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 16/16 Java 通过 16/16 Go 通过 16/16 JavaScript 通过 16/16 C++ 通过 16/16
最直接的递归是"从位置 i 开始，单独解码一个字符，或者合起来解码两个字符"。全是 1 的字符串，每个位置都有两种拆法，同一个后缀会被反复计算。下面是真实统计的递归调用次数，同时给出解码方式数：
不带记忆化的递归（全是 1 的字符串，每个位置都有两种拆法）：调用次数 n=10: 解码方式 89 种，递归调用 232 次， 0.03 ms；动态规划只要 10 步 n=20: 解码方式 10946 种，递归调用 28656 次， 3.46 ms；动态规划只要 20 步 n=25: 解码方式 121393 种，递归调用 317810 次， 49.83 ms；动态规划只要 25 步 n=30: 解码方式 1346269 种，递归调用 3524577 次， 615.97 ms；动态规划只要 30 步
解码方式数是斐波那契数（n = 10 时 89，n = 30 时 1346269），递归调用次数约是它的 2.6 倍（n = 30 时 3524577 次，615.97ms）；动态规划只需要 n 步。
字符串是 n 个 1，n 分别为 10、100、1000、10 万，每个规模取三次中最快的一次，基准是带记忆化的递归（也是线性，但每一步要走递归调用和缓存）：
字符串长度 n（全是 1） | 暴力解 | 本文解法
10 | 0.008 ms | 0.001 ms
100 | 0.074 ms | 0.014 ms
1000 | 0.824 ms | 0.179 ms
100000 | （未测，太慢） | 214.042 ms两者都是线性增长。n = 1000 时基准 0.824ms，动态规划 0.179ms，约 4.6 倍，差距来自递归调用的开销。动态规划从 1000 到 10 万（100 倍）增长约 1200 倍，超过线性：因为这里的答案是斐波那契数，n = 10 万时有两万多位，Python 的大整数加法本身也随位数增长；Java、Go、C++ 里题目限制答案在 32 位整数内，所以不会遇到这个问题。基准在 n = 10 万时没有测（递归深度太大）。
Python 版本另外和记忆化递归做了随机对拍：长度 1 到 12，多数以非 0 开头，数字偏向 0、1、2、6（这些数字最容易产生边界情形），另有少量任意以 0 开头的串：
随机对拍 30000 组（长度 1 到 12 的数字串（多数以非 0 开头，数字偏向 0、1、2、6；另有少量任意以 0 开头的串）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 16 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用 "2261"：dp[2]：最后一位 2 单独解码加上 dp[1] = 1，最后两位 22 合起来加上 dp[0] = 1，得 2；dp[3]：最后一位 6 单独加 dp[2] = 2，最后两位 26 合起来加 dp[1] = 1，得 3；dp[4]：最后一位 1 单独加 dp[3] = 3，最后两位 61 超过 26，不能合起来，得 3。答案 3（BBFA、VFA、BZA）。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。