解码方法与路径计数
将解码方法（数字到字母的映射）作为类似斐波那契的 DP 问题解决，然后统计可变步长楼梯中的路径数量。
解码方法与路径计数 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
解码方法问题
解码方法（LeetCode 91）将数字字符串映射为字母：'A'=1，'B'=2，……，'Z'=26。给定一个编码后的数字字符串，请计算其不同解码方式的数量。例如，'12' 可以解码为 'AB'（1+2）或 'L'（12），因此有 2 种方式。'226' 可以解码为 'BZ'（2+26）、'VF'（22+6）或 'BBF'（2+2+6），因此有 3 种方式。前导零会使某些解码方式无效。
# Encoding: A=1, B=2, ..., Z=26
# '12' → 'AB' or 'L' → 2 ways
# '226' → 'BZ' or 'VF' or 'BBF' → 3 ways
# '06' → invalid (no letter for '0')
# '10' → 'J' only → 1 way (only valid as 10, not 1+0)
s = '226'
print('Decodings for', s, ':', 3) # Expected: 3解码方法的 DP 公式
令 dp[i] 表示解码 s[:i] 的方法数。初始条件：dp[0] = 1（空字符串有一种解码方法）；如果 s[0] != '0'，则 dp[1] = 1，否则为 0。状态转移：如果 s[i-1] != '0'，就加上 dp[i-1]（单个数字解码）。如果 10 ≤ int(s[i-2:i]) ≤ 26，就加上 dp[i-2]（两个数字解码）。这本质上是带有效性检查的斐波那契模式。
def num_decodings(s):
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # empty prefix
dp[1] = 0 if s[0] == '0' else 1
for i in range(2, n + 1):
# Single digit decode
if s[i-1] != '0':
dp[i] += dp[i-1]
# Two digit decode
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i-2]
return dp[n]
print(num_decodings('12')) # 2
print(num_decodings('226')) # 3
print(num_decodings('06')) # 0前导零陷阱
解码方法中最棘手的部分是处理零。单独的“0”无法解码（没有字母对应 0），因此如果 s[i-1] == '0'，不要加上 dp[i-1]。作为第二个数字的“0”只有在两位数为 10 或 20 时才有效。“30”或“40”（以及更大的数）都无效，因为它们超过了 26。请始终检查 10 ≤ two_digit ≤ 26，而不只是检查 two_digit ≤ 26。
def num_decodings(s):
if not s or s[0] == '0': return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 # s[0] != '0' guaranteed by guard above
for i in range(2, n + 1):
one = int(s[i-1])
two = int(s[i-2:i])
if one != 0: dp[i] += dp[i-1] # valid single digit
if 10 <= two <= 26: dp[i] += dp[i-2] # valid two digits
return dp[n]
print(num_decodings('10')) # 1 (only 'J')
print(num_decodings('30')) # 0 (30 > 26, '0' alone invalid)
print(num_decodings('100')) # 0 (dp[2]=1 then '00' invalid, single '0' invalid)节省空间的解码方法
和斐波那契数列一样，解码方法的递推式只会回看两个位置，因此可以使用两个变量，将 O(n) 的空间降为O(1)。使用 prev2（前两个位置的值）和 prev1（前一个位置的值）。每一步都根据它们计算 curr，然后向前移动这两个变量。这与斐波那契数列的双变量优化完全相同。
def num_decodings_o1(s):
if not s or s[0] == '0': return 0
prev2 = 1 # dp[0]
prev1 = 1 # dp[1]
for i in range(2, len(s) + 1):
curr = 0
if s[i-1] != '0':
curr += prev1
two = int(s[i-2:i])
if 10 <= two <= 26:
curr += prev2
prev2, prev1 = prev1, curr
return prev1
print(num_decodings_o1('226')) # 3
print(num_decodings_o1('12')) # 2
print(num_decodings_o1('0')) # 0计算楼梯上的路径数
爬楼梯（LeetCode 70）的问题是：如果每次可以爬 1 级或 2 级，爬完 n 级楼梯有多少种方法？这正是斐波那契数列：ways(n) = ways(n-1) + ways(n-2)。ways(1)=1、ways(2)=2、ways(3)=3、ways(4)=5。当每次最多可以爬 k 级时，也可以将其推广为：ways(n) = sum(ways(n-1), ..., ways(n-k))。
def climb_stairs(n):
if n <= 2: return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
for i in range(1, 8):
print(f'climb_stairs({i}) = {climb_stairs(i)}')
# 1, 2, 3, 5, 8, 13, 21 — Fibonacci!步长可变的爬楼梯问题
当每次可以从给定集合中选择任意步长（例如 {1, 3, 5}）时，递推式变为 dp[i] = sum(dp[i-k] for k in steps if i-k >= 0)。为了节省内存，可以使用大小为 max(steps) 的滑动窗口。这是无界背包的计数变体——每种步长都可以使用任意多次。
def count_ways(n, steps):
dp = [0] * (n + 1)
dp[0] = 1 # one way to stay at ground
for i in range(1, n + 1):
for step in steps:
if i >= step:
dp[i] += dp[i - step]
return dp[n]
# Steps of 1 or 2 (classic climbing stairs)
print(count_ways(5, [1, 2])) # 8
# Steps of 1, 3, or 5
print(count_ways(5, [1, 3, 5])) # 5
# Steps of 2 or 3
print(count_ways(6, [2, 3])) # 3 (2+2+2, 3+3, 2+4-invalid, 2+2+2, 3+3, 3+2+1-no...)最小代价爬楼梯
最小代价爬楼梯（LeetCode 746）为每一级楼梯附加一个代价，并要求计算到达顶部的最小代价。从第 i 级可以跳到第 i+1 级或第 i+2 级。递推式为 dp[i] = cost[i] + min(dp[i-1], dp[i-2])。您可以从第 0 级或第 1 级开始。答案是 min(dp[n-1], dp[n-2])。
def min_cost_climbing(cost):
n = len(cost)
if n == 1: return cost[0]
dp = [0] * n
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, n):
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
return min(dp[-1], dp[-2]) # can start from step 0 or 1
print(min_cost_climbing([10, 15, 20])) # 15
print(min_cost_climbing([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) # 6解码方法 II：通配数字
解码方法 II（LeetCode 639）引入了通配字符“*”，它可以表示数字 1-9 中的任意一个。这会大幅增加有效解码的数量。单个“*”可以表示 9 种情况（分别表示数字 1-9）。两个“*”一起可以组成 9×9 种两位数组合，但其中只有不超过 26 的组合有效（11-19 有 9 种，21-26 有 6 种，因此“**”共有 15 种）。这需要进行仔细的分类讨论。
def num_decodings_ii(s):
MOD = 10**9 + 7
prev2, prev1 = 1, 9 if s[0] == '*' else (0 if s[0] == '0' else 1)
for i in range(1, len(s)):
curr = 0
c, p = s[i], s[i-1]
# Single digit
if c == '*': curr += 9 * prev1
elif c != '0': curr += prev1
# Two digits
if p == '*' and c == '*': curr += 15 * prev2 # 11-19(9) + 21-26(6)
elif p == '*': curr += (2 if c <= '6' else 1) * prev2
elif c == '*': curr += (9 if p == '1' else (6 if p == '2' else 0)) * prev2
else:
two = int(p + c)
if 10 <= two <= 26: curr += prev2
prev2, prev1 = prev1, curr % MOD
return prev1 % MOD
print(num_decodings_ii('*')) # 9
print(num_decodings_ii('1*')) # 18斐波那契数列的联系
解码方法和爬楼梯实际上都是伪装成其他形式的斐波那契类问题。任何满足 dp[i] 只依赖于 dp[i-1] 和 dp[i-2] 的 DP，都具有斐波那契结构，并且可以用 O(1) 的空间解决。有效性检查（零数字、步长）会改变哪些状态转移可以执行，但不会改变这种只回看两个位置的基本结构。在面试中迅速识别出这一类问题，是提高解题速度的重要模式。
# Fibonacci family: dp[i] = f(dp[i-1], dp[i-2])
# Fibonacci itself: dp[i] = dp[i-1] + dp[i-2]
# Climbing stairs: dp[i] = dp[i-1] + dp[i-2]
# Decode ways: dp[i] = (dp[i-1] if one_valid) + (dp[i-2] if two_valid)
# Min cost stairs: dp[i] = cost[i] + min(dp[i-1], dp[i-2])
# House robber: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# All solved with 2 rolling variables:
prev2, prev1 = 0, 1
for _ in range(10):
prev2, prev1 = prev1, prev1 + prev2
print('Fibonacci F(10):', prev1) # 89计算网格中的路径数
一个相关的计数问题是：给定一个 m×n 的网格，如果只能向右或向下移动，从左上角到右下角共有多少条不同路径？答案是二项式系数 C(m+n-2, m-1)。DP 解法会填充一个二维表格，其中 dp[i][j] = dp[i-1][j] + dp[i][j-1]。这是楼梯问题中斐波那契结构的二维版本——每个单元格的值等于上方单元格和左侧单元格之和。
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
# Or use math for O(1) solution
import math
def unique_paths_math(m, n):
return math.comb(m + n - 2, m - 1)
print(unique_paths(3, 7)) # 28
print(unique_paths_math(3, 7)) # 28
print(unique_paths(3, 3)) # 6面试易错点总结
解码方法中的常见错误包括：(1) 忘记单独的“0”无效——在加上 dp[i-1] 之前，始终检查 s[i-1] != '0'。(2) 只使用 two_digit <= 26，却没有检查 two_digit >= 10——“07”不应解码为“G”。(3) 返回 dp[n-1] 而不是 dp[n]——该表从 1 开始计数，因此 dp[n] 对应完整字符串。当您的 DP 表比输入多一个元素时，请务必再次检查数组下标。
# Common bug: checking two_digit <= 26 without >= 10
def buggy_decode(s):
dp = [0] * (len(s) + 1)
dp[0] = dp[1] = 1
for i in range(2, len(s) + 1):
if s[i-1] != '0': dp[i] += dp[i-1]
two = int(s[i-2:i])
# BUG: '07' gives two=7, and 7 <= 26 would add dp[i-2]
# Fix: require two >= 10
if 10 <= two <= 26: dp[i] += dp[i-2] # CORRECT
return dp[len(s)]
print(buggy_decode('06')) # 0 (correct, '0' alone invalid)
print(buggy_decode('07')) # 0 (correct, '07' not valid, '0' alone invalid)
print(buggy_decode('27')) # 1 (only 'BG', 27>26 so no two-digit)快速检查
请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学习了：解码方法遵循带有效性条件的类斐波那契递推式，分别处理单个数字（非零）和两个数字（10-26）的解码；爬楼梯和最小代价爬楼梯是可以用 O(1) 空间解决的纯斐波那契变体；以及识别出只回看两个位置的斐波那契类问题，能在面试中节省大量时间。接下来，我们将使用二维 DP 探索网格上的不同路径和最小路径和。
常见问题解答
「解码方法与路径计数」课时是免费的吗？
是的 — 「解码方法与路径计数」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「解码方法与路径计数」这节课中我会学到什么？
将解码方法（数字到字母的映射）作为类似斐波那契的 DP 问题解决，然后统计可变步长楼梯中的路径数量。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「解码方法与路径计数」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。