解码方法的动态规划解法：从字符串到字母序列
问题背景
给定一个只包含数字的字符串 s，我们需要计算它可以被解码为字母序列的不同方式数量。每个数字或数字组合对应一个字母：1 对应 ‘A’，2 对应 ‘B’，…，26 对应 ‘Z’。例如，字符串 “12” 可以解码为 “AB”（1, 2）或 “L”（12），共 2 种方式。然而，字符串可能包含前导零（例如 “06” 无法解码），且输入长度在 1 到 100 之间，答案保证是 32 位整数。本文将详细介绍如何使用动态规划高效解决这一问题。
为什么用动态规划？
这个问题具有明显的子问题重叠和最优子结构特性：
- 子问题：字符串
s[0:i]的解码方式依赖于s[0:i-1]和s[0:i-2]的解码方式。 - 最优子结构：通过组合子问题的解，我们可以构建整个问题的解。
- 重叠子问题：计算每个位置的解码方式时会重复利用之前的计算结果。
因此，动态规划是解决此问题的高效方法，优于递归或暴力枚举（后者可能导致指数级时间复杂度）。
解题思路
我们使用动态规划来计算解码方式数量。核心思想是将问题分解为更小的子问题，并通过状态转移方程逐步构建答案。
1. 定义状态
- 令
dp[i]表示字符串s的前i个字符（s[0:i]）可以解码的方案数。 - 目标是计算
dp[n]，其中n是字符串长度。
2. 初始化
- 空字符串：
dp[0] = 1，因为空字符串有一种解码方式（不解码）。 - 第一个字符：
- 如果
s[0] == '0'，无法解码，dp[1] = 0。 - 否则，
dp[1] = 1（例如 “1” 可解码为 ‘A’）。
- 如果
3. 状态转移
对于每个位置 i（从 2 到 n），我们考虑两种解码方式：
- 单个字符：如果当前字符
s[i-1]不是 ‘0’，它可以单独解码为一个字母，贡献dp[i-1]种方案。 - 两个字符：如果前两个字符
s[i-2:i]组成一个有效数字（10 到 26），可以解码为一个字母，贡献dp[i-2]种方案。 - 状态转移方程为：
dp[i] = (s[i-1] != '0' ? dp[i-1] : 0) + (s[i-2:i] 在 10 到 26 之间 ? dp[i-2] : 0)
4. 边界条件
- 如果字符串以 ‘0’ 开头，直接返回 0，因为前导零无法解码。
- 检查两个字符组合时，确保数字在 10 到 26 之间，且没有前导零（例如 “06” 无效）。
5. 空间优化
由于 dp[i] 只依赖于 dp[i-1] 和 dp[i-2]，我们可以用两个变量（dp_prev1 和 dp_prev2）代替数组，优化空间复杂度到 O(1)。
代码实现
以下是带详细中文注释的代码：
/**
* 解码方法：计算数字字符串可以解码为字母序列的不同方式数量
* 每个数字或数字组合对应字母：1 -> 'A', 2 -> 'B', ..., 26 -> 'Z'
*/
class Solution {
public int numDecodings(String s) {
// 边界情况：空字符串或首字符为 '0'，无法解码，返回 0
if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
int n = s.length();
// 使用两个变量模拟 dp 数组，优化空间复杂度
int dp_prev2 = 1; // dp[0]，空字符串有一种解码方式
int dp_prev1 = 1; // dp[1]，初始化为第一个字符的解码方式
// 从第二个字符开始遍历
for (int i = 2; i <= n; i++) {
int curr = 0; // 当前位置 dp[i] 的值
// 检查单个字符 s[i-1] 是否可以解码
if (s.charAt(i-1) != '0') {
curr += dp_prev1; // 继承 dp[i-1] 的方案
}
// 检查两个字符 s[i-2:i] 是否可以解码
if (i >= 2) {
int num = Integer.parseInt(s.substring(i-2, i)); // 取前两个字符
// 确保数字在 10 到 26 之间
if (num >= 10 && num <= 26) {
curr += dp_prev2; // 继承 dp[i-2] 的方案
}
}
// 更新滚动变量
dp_prev2 = dp_prev1;
dp_prev1 = curr;
}
// 返回最终结果 dp[n]
return dp_prev1;
}
}
复杂度分析
- 时间复杂度：O(n)，遍历字符串一次，每次操作（比较和解析）为 O(1)。
- 空间复杂度：O(1)，仅使用两个变量存储状态。
示例分析
以示例 “226” 为例：
- 初始化：
dp[0] = 1,dp[1] = 1（”2” -> ‘B’）。 i=2：检查 “2”（有效，+dp[1]=1），检查 “22”（有效，+dp[0]=1），dp[2] = 2。i=3：检查 “6”（有效，+dp[2]=2），检查 “26”（有效，+dp[1]=1），dp[3] = 3。- 输出：3（”BZ”, “VF”, “BBF”）。
对于 “06”：
- 首字符 ‘0’，无法解码，返回 0。
总结
通过动态规划，我们将问题分解为子问题，利用状态转移方程高效计算解码方式数量。优化后的代码不仅时间复杂度低（O(n)），而且通过滚动变量将空间复杂度降到 O(1)。这种方法能够处理所有边界情况（包括前导零和长字符串），是解决此类字符串解码问题的经典范例。