题目

思路

一句话本质：从第一个数字走到末尾，每步可选「走 1 个字符」或「走 2 个字符」，但每步落下的片段必须落在合法码 1–26 上，这是一个带合法性判断的路径计数问题。

最直白的做法：在每个位置做选择——要么把当前字符单独切开，要么把它和后一个字符一起切开；遇到不合法的片段就回溯。最坏情况下每个位置都有两种选择，搜索树接近满二叉树，时间复杂度为 O(2ⁿ)。而 n 最大可达 100，这个规模完全无法承受。

关键观察：假设我们已经知道「前 i-1 个字符」的方案数 dp[i-1] 和「前 i-2 个字符」的方案数 dp[i-2]，那么看当前前缀 s[0..i-1]：

• 若最后一位 s[i-1] 落在 1–9，它可单独成码，方案来自 dp[i-1]；
• 若最后两位 s[i-2..i-1] 落在 10–26，它们可一起成码，方案来自 dp[i-2]。

两种来源互不重叠，直接相加即可。而 dp[i] 只依赖 dp[i-1] 与 dp[i-2] 两个前状态，重叠子问题非常明显，因此可以线性扫一遍。

选定做法：自底向上 DP，令 dp[i] 表示前 i 个字符的合法解码方案数，按上述转移从 i=2 推到 i=n。

解法

按四步实现：

1. 定义 dp[i] 为 s 前 i 个字符的合法解码方案数。
2. 初始化 dp[0] = 1（空串只有一种空方案）；若 s[0] == '0'，直接返回 0，否则 dp[1] = 1。
3. 从 i=2 到 n 转移：单字符 1–9 合法则加 dp[i-1]；双字符 10–26 合法则加 dp[i-2]。
4. 返回 dp[n]。

以 s = "121" 走一遍：