题目定位
每个位置可以按一位或两位解码，只要对应编码合法，因此它是典型的前缀决策型 DP。
关键观察
转移完全取决于最后一位和最后两位是否都能形成合法字母。
目标复杂度
O(n) / O(n)
这题的解法思路怎么拆
1
每个位置可以按一位或两位解码，只要对应编码合法，因此它是典型的前缀决策型 DP。
2
转移完全取决于最后一位和最后两位是否都能形成合法字母。
3
先用自然语言命名状态。
4
列出哪些决策会转移到这个状态。
参考实现
Python# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = transition(dp, i)
# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = transition(dp, i, j)
常见坑点
warning
把前导 0 当成可解码字符。
warning
没有分别判断一位和两位编码是否合法。
高频追问
能否把空间压到常数？
为什么这里不能贪心解？
继续刷相关题
先把 动态规划 这个模式刷成体系，再去做更难变体。