LeetCode 91中等动态规划 · 字符串
解码方法 图解题解
这道题到底在问什么
数字串按 A=1 到 Z=26 解码，求总方案数。
- s
- "226"
- 输出
- 3
最优解：一步一步想明白
- 3关键不是背模板，而是看懂为什么这题适合动态规划 · 字符串。
- 4dp[i] 表示「前 i 个字符」有多少种解码法。先填 dp[0]=1、dp[1]=1。
- 5每个 dp[i] 有两条来路。先看末 1 位 '2'：在 1~9 能单独成字母(2→B)→ 继承 dp[1]。
- 6再看末 2 位 '22'=22(在 10~26，对应 V)→ 也能合并解码 → 加 dp[0]。两条来路相加 dp[2]=2。
- 7轮到 dp[3]。末 1 位 '6' 在 1~9 → 继承 dp[2]=2。
- 8末 2 位 '26'=26(恰在 10~26，对应 Z)→ 再加 dp[1]=1 → dp[3]=3。
- 9关键帧：每位都有「末 1 位单独(1~9)」和「末 2 位合并(10~26)」两条来路，方案数相加。"226" 的 3 种：2·2·6、22·6、2·26。
- 12把这句话记住，下次遇到同类题，就能更快选出方向。
⚠️ 容易写错的地方
✗ 错：把 0 当成单独字符解码
✓ 对：0 只能和前一位组成 10 或 20
单独 0 没有字母对应
✗ 错：两位组合只判 ≤26、忘判 ≥10
✓ 对：两位必须落在 10~26 才合法
"06" 虽 ≤26 但 <10(前导 0)，不是合法两位字母，不能加 dp[i-2]。
✗ 错：变量名和动画不一致
✓ 对：代码变量沿用动画里的核心名字
学习时最怕脑内维护两套概念
完整代码（Python / C++ / Java）
Python
class Solution:
def numDecodings(self, s):
if not s or s[0] == "0":
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
if s[i - 1] != "0": # 末1位 1~9 可单独
dp[i] += dp[i - 1]
two = int(s[i - 2:i])
if 10 <= two <= 26: # 末2位 10~26 可合并
dp[i] += dp[i - 2]
return dp[n]C++
class Solution {
public:
int numDecodings(string s) {
if (s.empty() || s[0] == '0') return 0;
int n = s.size();
vector<int> dp(n + 1, 0);
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
if (s[i-1] != '0') dp[i] += dp[i-1]; // 末1位 1~9
int two = (s[i-2] - '0') * 10 + (s[i-1] - '0');
if (two >= 10 && two <= 26) dp[i] += dp[i-2]; // 末2位 10~26
}
return dp[n];
}
};Java
class Solution {
public int numDecodings(String s) {
if (s.isEmpty() || s.charAt(0) == '0') return 0;
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
if (s.charAt(i-1) != '0') dp[i] += dp[i-1]; // 末1位 1~9
int two = (s.charAt(i-2) - '0') * 10 + (s.charAt(i-1) - '0');
if (two >= 10 && two <= 26) dp[i] += dp[i-2]; // 末2位 10~26
}
return dp[n];
}
}套路模板 · 动态规划 · 字符串
# 解码方法骨架 · 带约束的爬楼梯
dp[0] = dp[1] = 1
for i in range(2, n+1):
if s[i-1] != "0": # 末1位 1~9 可单独解码
dp[i] += dp[i-1]
if 10 <= int(s[i-2:i]) <= 26: # 末2位 10~26 可合并
dp[i] += dp[i-2]
return dp[n]复杂度
时间复杂度
O(n)
扫一遍字符串，每位 O(1) 转移
空间复杂度
O(n)
dp 数组 O(n)，只用前两项可滚动到 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 解码方法 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么像爬楼梯但更难？+
框架 dp[i]=dp[i-1]+dp[i-2]，但每步要判合法：1 位须 1-9、2 位须 10-26，0 是大坑。
0 怎么处理？+
0 没有对应字母不能单独解码，只能作 10 或 20 的个位；其余含 0(如 30、06)无解、方案 0。
复杂度？+
O(n) 时间、可滚动到 O(1) 空间。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。