动态规划解析：解码方法问题

动态规划解析：解码方法问题

• • 1. 问题描述
  • 2. 解题思路
  • • 2.1 动态规划
    • 2.2 关键点
  • 3. 代码实现
  • 4. 代码解析
  • • 4.1 初始化检查
    • 4.2 DP数组初始化
    • 4.3 状态转移
  • 5. 复杂度分析
  • 6. 测试用例
  • 7. 关键点总结
  • 8. 扩展思考

1. 问题描述

给定一个只包含数字的非空字符串 s，按照字母A-Z的编码规则（1→A，2→B，…，26→Z），计算字符串可以被解码的方法总数。注意：

• “06” 不能解码为 “F”（因为前导零）
• 无法解码的字符串返回0

示例1：

输入: s = \"12\"输出: 2解释: \"AB\"(1 2) 或 \"L\"(12)

示例2：

输入: s = \"226\"输出: 3解释: \"BZ\"(2 26), \"VF\"(22 6), \"BBF\"(2 2 6)

2. 解题思路

2.1 动态规划

1. 状态定义：dp[i]表示前i个字符的解码方法数
2. 转移方程：
   • 当前字符单独解码（非零）：dp[i] += dp[i-1]
   • 当前字符与前一个字符组合解码（10-26）：dp[i] += dp[i-2]
3. 边界条件：
   • dp[0] = 1（空字符串有1种解码方式）
   • dp[1]取决于第一个字符是否为’0’

2.2 关键点

• 处理前导零的情况
• 有效组合的判断（10-26）
• 空间优化（只保留前两个状态）

3. 代码实现

#include #include int numDecodings(char* s) { int n = strlen(s); if (n == 0 || s[0] == \'0\') return 0; // 初始化DP数组 int* dp = (int*)malloc((n + 1) * sizeof(int)); dp[0] = 1; // 空字符串 dp[1] = 1; // 第一个字符（非零） for (int i = 2; i <= n; i++) { dp[i] = 0; // 当前字符单独解码（非零） if (s[i-1] != \'0\') { dp[i] += dp[i-1]; } // 当前字符与前一个字符组合解码 int twoDigit = (s[i-2] - \'0\') * 10 + (s[i-1] - \'0\'); if (twoDigit >= 10 && twoDigit <= 26) { dp[i] += dp[i-2]; } } int result = dp[n]; free(dp); return result;}

4. 代码解析

4.1 初始化检查

if (n == 0 || s[0] == \'0\') return 0;

• 空字符串或前导零直接返回0

4.2 DP数组初始化

dp[0] = 1; // 空字符串dp[1] = 1; // 第一个字符（非零）

• 空字符串有1种解码方式（基础情况）
• 第一个字符非零时有1种解码方式

4.3 状态转移

// 单独解码if (s[i-1] != \'0\') { dp[i] += dp[i-1];}// 组合解码int twoDigit = (s[i-2] - \'0\') * 10 + (s[i-1] - \'0\');if (twoDigit >= 10 && twoDigit <= 26) { dp[i] += dp[i-2];}

• 当前字符非零时可单独解码
• 前两个字符组合在10-26范围内时可组合解码

5. 复杂度分析

• 时间复杂度：O(n)，只需遍历字符串一次
• 空间复杂度：O(n)，DP数组空间（可优化到O(1)）

6. 测试用例

测试用例1：

s = \"12\"// 预期输出: 2

测试用例2：

s = \"226\"// 预期输出: 3

测试用例3：

s = \"06\"// 预期输出: 0

7. 关键点总结

✅ 动态规划：状态转移方程的建立
✅ 边界处理：前导零和空字符串的特殊情况
✅ 有效组合判断：10-26的有效范围
✅ 空间优化：可只保留前两个状态

8. 扩展思考

• 如何输出所有可能的解码方式？
• 如何优化空间复杂度到O(1)？
• 如何处理更长的字符串（n>100）？

📌 总结：解码方法问题展示了动态规划处理字符串问题的典型应用，通过分析子问题和状态转移，可以高效计算解码方式总数。掌握这种方法对解决类似计数问题很有帮助！