经典动态规划问题

解题思路

这是一个典型的动态规划问题。我们可以定义一个状态数组 dp[i]，表示前 i 个字符的解码方式数。

动态规划状态定义

• dp[i]：表示前 i 个字符的解码方式数

状态转移方程

对于第 i 个位置，我们有两种可能的选择：

1. 单独解码第 i 个字符：

   • 如果当前字符不是 '0'（可以单独解码），则 dp[i] += dp[i-1]

2. 与前一个字符组合解码：

   • 如果当前字符和前一个字符组成的两位数在 10-25 之间，则 dp[i] += dp[i-2]

初始条件

• dp[0] = 1：空字符串有一种解码方式（不选任何字符）
• dp[1] = 1：如果第一个字符不是 '0'；否则为 0

边界情况处理

• 如果字符串以 '0' 开头，直接返回 0（无法解码）
• 对于任何位置的 '0'，只能与前一个字符组合成 10 或 20