LeetCode 91 Decode Ways 解码方式计数：从递归到动态规划的四种递进解法（附多语言源码）

LeetCode 91 Decode Ways 解码方式计数：从递归到动态规划的四种递进解法（附多语言源码）

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

本文围绕 LeetCode 第 91 题「Decode Ways」展开，讲解如何统计一条仅含数字的字符串可以被映射为字母（A–Z对应1–26）的所有合法解码方式。文章以仓库内 hints/decode-ways.md 的解题提示为主线，完整继承其关于复杂度目标、决策树递推关系、备忘录缓存与边界条件的四个递进式提示，并结合 articles/decode-ways.md 的详细推导，给出从朴素递归（$O(2^n)$）到记忆化搜索、自底向上 DP、空间优化 DP（$O(n)$ 时间 / $O(1)$ 空间）的完整演进路径。读完本文，你将掌握该题的递推建模、两种 DP 实现范式以及前导零等边界陷阱的规避方法，并能对照仓库中 C、C++、Go、Java、JavaScript、Python、Rust、TypeScript 等多语言实现进行交叉验证。

1. 问题定义与字母映射规则

题目给出一条只包含数字字符的字符串s，要求返回所有可能的解码方法总数。映射规则为：

• "1"→"A"，"2"→"B"，…，"26"→"Z"

也就是说，一个映射值可以是1 位数字（1–9），也可以是2 位数字（10–26）。仓库中 cpp/0091-decode-ways.cpp 的文件头注释给出了两个直观示例：

• s = "12"→ 2 种："AB"（1 2）或"L"（12）
• s = "226"→ 3 种："2 26"、"22 6"、"2 2 6"

关键约束（来自 articles/decode-ways.md 的 Prerequisites 与递归章节）：

• 单数字解码：s[i]不能为'0'，因为没有任何字母映射到0；
• 双数字解码：s[i:i+2]必须落在10–26区间内；
• 字符串中的'0'只能作为双数字的第二位（如"10"、"20"）出现，否则该子串不可解码。

2. 复杂度目标：以 $O(n)$ 时间和 $O(n)$ 空间为基准

hints/decode-ways.md 的开篇提示（Recommended Time & Space Complexity）明确要求：

目标解法应达到或优于$O(n)$ 时间、$O(n)$ 空间，其中n为给定字符串长度。

这一目标直接决定了思路走向：$O(n)$ 意味着不能枚举全部解码组合（那是 $O(2^n)$），必须利用子问题的重叠性做动态规划或记忆化搜索。后文四种解法正是围绕"如何从 $O(2^n)$ 收敛到 $O(n)$"展开的。

3. 建模核心：决策树与递推关系（Hint 1 & Hint 2）

3.1 每个位置只有两种选择

hints/decode-ways.md 的 Hint 1 指出：由于映射值最多 2 位，扫描字符串时可以把一个或两个连续数字组合起来探索所有可能的解码路径，这本质是一棵决策树。在任意下标i处只有两种选择：

1. 取一位s[i]，要求s[i] != '0'；
2. 取两位s[i:i+2]，要求数值落在10–26。

3.2 递推关系

Hint 2 进一步给出递推骨架：从下标i开始解码的方式数等于

$$dfs(i) = dfs(i + 1) + dfs(i + 2)$$

其中dfs(i + 1)对应"取一位"分支，dfs(i + 2)对应"取两位"分支。但并不是每次两个分支都合法——前导零、超过26的两位数都构成非法路径，这正是后文边界条件的重点。

以s = "226"为例的决策树（由 articles/decode-ways.md 的递归直觉推导）：

dfs(0) "226" ├── 取一位 "2" → dfs(1) "26" │ ├── 取一位 "2" → dfs(2) "6" → 取一位 "6" → dfs(3) = 1 (2-2-6) │ └── 取两位 "26" → dfs(3) = 1 (2-26) └── 取两位 "22" → dfs(2) "6" → 取一位 "6" → dfs(3) = 1 (22-6) 合计 = 3

4. 解法一：朴素递归（Brute Force DFS）

4.1 基例与递归逻辑

articles/decode-ways.md 的递归章节给出的算法骨架：

1. 定义dfs(i)= 解码s[i:]的方式数；
2. 基例：
   • i == len(s)→ 返回1（整串解码完成，当前路径计 1 次）；
   • s[i] == '0'→ 返回0（非法起点）；
3. 递归求和：先取一位dfs(i + 1)；若两位数字合法（10–26）再加dfs(i + 2)；
4. 从dfs(0)开始。

Python 实现（与 python/0091-decode-ways.py 中的递归思路一致）：

class Solution: def numDecodings(self, s: str) -> int: def dfs(i): if i == len(s): return 1 if s[i] == '0': return 0 res = dfs(i + 1) if i < len(s) - 1: if (s[i] == '1' or (s[i] == '2' and s[i + 1] < '7')): res += dfs(i + 2) return res return dfs(0)

4.2 复杂度：$O(2^n)$ 的指数灾难

递归每次至多分叉两次，最坏情况下（如全"1"串）会形成指数级调用树。但注意：大量调用携带相同的参数i，重复计算同一子问题。

• 时间复杂度：$O(2^n)$（来自 articles/decode-ways.md 递归章节；hints/decode-ways.md 的 Hint 3 也明确指出暴力递归为 $O(2^n)$）
• 空间复杂度：$O(n)$（递归调用栈深度）

这一版本适合理解递推本质，但无法通过大规模测试用例，必须消除重复计算。

5. 解法二：自顶向下 DP（记忆化搜索）

5.1 核心观察：子问题重叠

hints/decode-ways.md 的 Hint 3 与 Hint 4 给出两条关键指引：

• Hint 3：考虑重复调用同参数递归造成的重复工作，想办法避免它，并思考递归函数的基例；
• Hint 4：基例是i越界时返回1；当前位为'0'时返回0；使用数组或哈希表缓存递归结果，命中缓存直接返回。

5.2 算法步骤

1. 用字典dp记录dp[i]= 解码s[i:]的方式数；
2. 初始化dp[len(s)] = 1（空串视为 1 种合法解码，对应基例）；
3. dfs(i)：命中缓存直接返回；s[i] == '0'返回0；否则计算dfs(i + 1)，两位数合法时加dfs(i + 2)；
4. 结果存入dp[i]后返回；最终调用dfs(0)。

Python 实现（即 python/0091-decode-ways.py 的 Memoization 版本）：

class Solution: def numDecodings(self, s: str) -> int: dp = {len(s): 1} def dfs(i): if i in dp: return dp[i] if s[i] == "0": return 0 res = dfs(i + 1) if i + 1 < len(s) and ( s[i] == "1" or s[i] == "2" and s[i + 1] in "0123456" ): res += dfs(i + 2) dp[i] = res return res return dfs(0)

注意两位数的合法性判断有两种等价写法（articles/decode-ways.md 中多语言版本均有体现）：

• 字符比较法：s[i] == '1' or (s[i] == '2' and s[i + 1] < '7')
• 集合包含法：s[i] == '1' or s[i] == '2' and s[i + 1] in "0123456"

两者都精确限定两位数字在10–26区间：以'1'开头时第二位可为0–9；以'2'开头时第二位只能是0–6。

5.3 复杂度

• 时间复杂度：$O(n)$——每个下标至多计算一次；
• 空间复杂度：$O(n)$——缓存字典（或数组）加递归栈。

仓库的 go/0091-decode-ways.go 提供了用切片dp代替哈希表的记忆化实现，rust/0091-decode-ways.rs 则用Vec<Option<i32>>区分"未计算"与"已缓存"状态，可作为不同语言惯用写法的参考。

6. 解法三：自底向上 DP（Tabulation）

6.1 反转视角

自底向上不再递归，而是从后往前构建答案（articles/decode-ways.md 的 Bottom-Up 章节）：

• dp[i]= 解码子串s[i:]的方式数，最终答案是dp[0]；
• 每个位置只依赖其后1 或 2 个位置，天然适合迭代填表。

6.2 算法步骤

1. 建立 DP 表，基例dp[len(s)] = 1；
2. 从i = len(s) - 1向左迭代：
   • s[i] == '0'→dp[i] = 0；
   • 否则dp[i] = dp[i + 1]（取一位），若两位数合法则再加dp[i + 2]；
3. 返回dp[0]。

Python 实现（即 python/0091-decode-ways.py 的 Dynamic Programming 版本）：

class Solution: def numDecodings(self, s: str) -> int: dp = {len(s): 1} for i in range(len(s) - 1, -1, -1): if s[i] == "0": dp[i] = 0 else: dp[i] = dp[i + 1] if i + 1 < len(s) and ( s[i] == "1" or s[i] == "2" and s[i + 1] in "0123456" ): dp[i] += dp[i + 2] return dp[0]

6.3 另一种等价视角：从前往后

仓库 cpp/0091-decode-ways.cpp 采用从前向后的递推写法，递推关系为：

dp[i] += dp[i-1] (若 s[i-1] 是 1~9) dp[i] += dp[i-2] (若 s[i-2:i] 是 10~26)

class Solution { public: int numDecodings(string s) { if (s[0] == '0') { return 0; } int n = s.size(); vector<int> dp(n + 1); dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { int ones = stoi(s.substr(i - 1, 1)); if (ones >= 1 && ones <= 9) { dp[i] += dp[i - 1]; } int tens = stoi(s.substr(i - 2, 2)); if (tens >= 10 && tens <= 26) { dp[i] += dp[i - 2]; } } return dp[n]; } };

c/0091-decode-ways.c 同样给出 C 语言的自底向上版本，并显式处理了n == 1与末尾为'0'的基例：

int numDecodings(char * s){ int n = strlen(s); if (n==1) return s[0]!='0'; int* dp = malloc(sizeof(int)*(n+1)); dp[n] = 1; // 空串视为 1 种 dp[n-1] = s[n-1]=='0'?0:1; // 末尾为 '0' 则非法 for (int i=n-2; i>=0; i--) { if (s[i]=='0') { dp[i] = 0; } else if (s[i]=='1' || s[i]=='2') { if (s[i]=='2' && s[i+1]>='7') dp[i] = dp[i+2]; // 如 "27" 只能拆单 else dp[i] = dp[i+1] + dp[i+2]; // 两条分支都合法 } else { dp[i] = dp[i+1]; // 如 "3"~"9" 只能拆单 } } return dp[0]; }

6.4 复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$（DP 表长度n + 1）

7. 解法四：空间优化 DP（$O(1)$ 空间）

7.1 关键观察

从自底向上版本可知（articles/decode-ways.md 的 Space Optimized 章节）：dp[i]只依赖dp[i+1]和dp[i+2]，因此无需维护整张表，只需两个滚动变量：

• dp1→ 从i + 1开始解码的方式数；
• dp2→ 从i + 2开始解码的方式数。

7.2 算法步骤

1. 初始化dp1 = 1（对应dp[len(s)]）、dp2 = 0；
2. 从右向左迭代：
   • s[i] == '0'→ 当前结果dp = 0；
   • 否则dp = dp1，若两位数合法再dp += dp2；
3. 每轮结束滚动更新：dp2 = dp1、dp1 = dp；
4. 返回dp1。

Python 实现：

class Solution: def numDecodings(self, s: str) -> int: dp = dp2 = 0 dp1 = 1 for i in range(len(s) - 1, -1, -1): if s[i] == "0": dp = 0 else: dp = dp1 if i + 1 < len(s) and ( s[i] == "1" or s[i] == "2" and s[i + 1] in "0123456" ): dp += dp2 dp, dp1, dp2 = 0, dp, dp1 return dp1

7.3 复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

仓库 javascript/0091-decode-ways.js 的第三种实现（2 Pointer 版本）进一步展示了从左向右的滚动指针写法，用prev与prevPrev两个变量在单次遍历中完成相同的递推，并单独抽出isTwoDigit判断函数：

var isTwoDigit = (s, i) => { const [prevChar, curChar] = [s[i - 1], s[i]]; const is10 = prevChar === '1'; const is20 = prevChar === '2' && curChar <= '6'; return is10 || is20; };

这四种解法在 articles/decode-ways.md 中均配有 Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 的完整 tab 版本，可以按语言习惯对照阅读。

8. 常见陷阱与边界情况

articles/decode-ways.md 的 Common Pitfalls 章节总结了三个最容易被忽略的坑，hints/decode-ways.md 的 Hint 1 与 Hint 4 也分别提示了"并非所有两位数合法"与"前导零非法"。

8.1 未处理前导零

以'0'开头或无法与前一位配对的'0'会使整个子串解码数为 0。这是最常见的漏判点：

# Wrong: 不处理 '0' 的情况 res = dfs(i + 1) # Correct: '0' 无字母映射，返回 0 if s[i] == '0': return 0 res = dfs(i + 1)

典型反例：s = "0"→ 0 种；s = "01"→ 0 种；s = "10"→ 1 种（只有"J"，"1"与"0"不能拆开，因为"0"无法单独解码）。

8.2 两位数合法性校验错误

两位数字只有当数值落在10–26之间才合法。常见的错误是不校验直接累加，从而把"00"、"07"、"30"等非法组合计入：

# Wrong: 允许 "00"、"30" 等非法两位数 if i + 1 < len(s): res += dfs(i + 2) # Correct: 仅允许 10-26 if i + 1 < len(s) and (s[i] == '1' or (s[i] == '2' and s[i + 1] <= '6')): res += dfs(i + 2)

8.3 基例值混淆

当i越过字符串末尾（整串解码成功）时，应返回1——表示"从起点到这里的这一条路径是 1 种完整解码"。若误返回 0，所有路径都会被计为 0：

# Wrong: 返回 0 导致全部计数归零 if i == len(s): return 0 # Correct: 到达末尾意味着一条完整解码路径 if i == len(s): return 1

另外注意：自底向上版本中的dp[len(s)] = 1正是这一基例在迭代形式下的对应物，二者必须保持一致。

9. 仓库中的多语言实现索引

本题在仓库中属于完成度较高的题目之一，README.md 的题解总表中标记0091 - Decode Ways在 C、C++、C#、Go、Java、JavaScript、Kotlin、Python、Rust、TypeScript、Swift 等语言下均有实现，可对照阅读：

各语言实现共同印证了同一套核心逻辑：单数字解码要求非零，双数字解码要求落在10–26，子问题结果可缓存复用。读者可以选取自己熟悉的语言，在本地运行几个代表性用例（"12"→ 2，"226"→ 3，"06"→ 0，"10"→ 1）验证上述四种解法的输出一致性。

总结

Decode Ways 是掌握"一维线性 DP 建模"的经典入门题，其要点可归纳为：

1. 建模：每个位置只有"取一位 / 取两位"两种分支，递推关系为dfs(i) = dfs(i + 1) + dfs(i + 2)，但需以合法性为前提；
2. 收敛：朴素递归 $O(2^n)$ 因大量重叠子问题而失效，通过记忆化（自顶向下）或填表（自底向上）收敛到 $O(n)$ 时间；
3. 优化：利用"只依赖后两个位置"的特性，用两个滚动变量把空间压到 $O(1)$；
4. 边界：前导零、两位数字区间（10–26）校验、基例返回1，三者缺一不可。

沿 hints/decode-ways.md 的四个提示顺序思考（复杂度目标 → 决策树递推 → 消除重复 → 基例与缓存），配合 articles/decode-ways.md 的多语言完整实现与仓库源码交叉验证，即可彻底吃透这一经典 DP 问题。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode