LeetCode 91题解码方法：动态规划解法与边界处理-平芜编程栈

1. 问题概述与核心难点

LeetCode 91题"Decode Ways"是一个经典的动态规划问题，要求计算给定数字字符串的解码方式总数。题目描述为：一条包含字母A-Z的消息通过'A'->1，'B'->2...'Z'->26的方式进行了编码。给定一个只包含数字的非空字符串，请计算解码方法的总数。

这个问题的核心难点在于处理数字字符串中的边界条件：

数字'0'不能单独解码（没有字母对应0）
两位数组合必须在10-26之间才有效
需要处理连续'0'和无效数字序列的情况

我在实际面试中多次遇到这个问题变形，发现90%的面试者都会在初始解法中遗漏至少一个边界条件。下面通过完整解法展示如何系统化处理这些陷阱。

2. 动态规划解法详解

2.1 状态定义与转移方程

我们定义dp[i]表示前i个字符的解码方式数。考虑最后一个字符的解码方式：

单独解码s[i]（要求s[i] != '0'）： dp[i] += dp[i-1]
组合解码s[i-1]和s[i]（要求i>1且10<=s[i-1:i]<=26）： dp[i] += dp[i-2]

初始条件：

dp[0] = 1（空字符串有1种解码方式）
dp[1] = 1（当s[0] != '0'）

def numDecodings(s: str) -> int: if not s or s[0] == '0': return 0 n = len(s) dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): # 处理单个字符 if s[i-1] != '0': dp[i] += dp[i-1] # 处理两个字符组合 two_digit = int(s[i-2:i]) if 10 <= two_digit <= 26: dp[i] += dp[i-2] return dp[n]

2.2 空间优化技巧

观察到dp[i]只依赖前两个状态，可以将空间复杂度从O(n)优化到O(1)：

def numDecodings(s: str) -> int: if not s or s[0] == '0': return 0 prev1 = prev2 = 1 # dp[0]和dp[1] for i in range(1, len(s)): current = 0 if s[i] != '0': current += prev1 two_digit = int(s[i-1:i+1]) if 10 <= two_digit <= 26: current += prev2 prev2, prev1 = prev1, current return prev1

3. 边界条件处理实战

3.1 零值处理要点

零值是最容易出错的边界条件，需要特别注意：

字符串以'0'开头直接返回0（无法解码）
中间出现'0'时：
- 必须与前一个字符组合（'10'或'20'有效）
- 其他组合（如'00','30'）直接返回0

测试用例验证：

assert numDecodings("101") == 1 # 10,1 assert numDecodings("100") == 0 # 10,0无效 assert numDecodings("110") == 1 # 1,10 或 11,0(无效)

3.2 大数处理技巧

当字符串长度超过1000时，需要注意：

Python无需处理整数溢出
其他语言可能需要模运算（如1e9+7）
实际面试中可以询问是否需要考虑大数情况

4. 算法复杂度分析

时间复杂度：

单次遍历字符串：O(n)
每个字符进行常数次操作

空间复杂度：

基础解法：O(n)的dp数组
优化解法：O(1)的滚动变量

5. 常见错误与调试技巧

5.1 典型错误模式

忽略前导零：

# 错误实现示例 def wrong(s): if not s: return 0 dp = [0]*(len(s)+1) dp[0] = 1 # 缺少对s[0]=='0'的判断

无效组合判断不完整：

# 错误示例：未检查两位数范围 if int(s[i-1:i]) > 0: # 应该检查10-26 dp[i] += dp[i-2]

5.2 调试建议

使用简单测试用例验证：
- "" → 1
- "0" → 0
- "10" → 1
- "27" → 1

打印dp数组检查中间状态：

print(f"i={i}, s[i-1]={s[i-1]}, two_digit={two_digit}, dp={dp}")

6. 问题变种与扩展

6.1 输出所有解码方式

如果需要输出具体解码方案（而不仅是计数），可以使用回溯法：

def decodeWays(s): res = [] def backtrack(index, path): if index == len(s): res.append(''.join(path)) return if s[index] != '0': path.append(chr(ord('A') + int(s[index]) - 1)) backtrack(index + 1, path) path.pop() if index < len(s) - 1 and 10 <= int(s[index:index+2]) <= 26: path.append(chr(ord('A') + int(s[index:index+2]) - 1)) backtrack(index + 2, path) path.pop() backtrack(0, []) return res

6.2 编码方式变种

如果编码规则变化（如'A'->0），只需要修改：

零值处理逻辑
有效数字范围判断

7. 实际面试技巧

沟通策略：
- 先说明暴力解法（递归+记忆化）
- 再优化到动态规划
- 最后讨论空间优化
测试用例设计：
- 必须包含的测试案例：
  - 空字符串
  - 全零序列
  - 包含'0'的有效/无效组合
  - 最大值边界（'26' vs '27'）
代码书写规范：
- 先处理边界条件
- 变量命名清晰（prev1/prev2比a/b更好）
- 添加必要注释