线性动态规划：解码方法

字数 2152 2025-10-26 11:43:54

线性动态规划：解码方法

题目描述
一条包含字母 A-Z 的消息通过以下映射进行了编码：
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
现在，给定一个只包含数字的非空字符串 s，请计算并返回解码方法的总数。题目数据保证答案肯定是一个 32 位的整数。

示例 1
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6)。

示例 3
输入：s = "06"
输出：0
解释："06" 无法映射到 "F"，因为 "06" 不能视为 6。这是因为零不能单独存在，且数字不能以零开头。

解题过程
我们使用动态规划来解决这个问题。核心思想是：定义 dp[i] 表示字符串 s 的前 i 个字符（即 s[0..i-1]）的解码方法数。我们需要找出 dp[i] 与之前状态的关系。

定义状态
设 dp[i] 表示前 i 个字符的解码方法总数。
初始化基础情况
- dp[0] = 1：空字符串有一种解码方式（可以将其视为解码的起点，一个合理的基准）。
- 对于第一个字符（i=1）：
  - 如果 s[0] 是 '0'，则无法解码，直接返回 0。
  - 否则，dp[1] = 1。
状态转移方程（核心）
对于每个位置 i（从 2 到 n，n 为字符串长度），我们考虑最后一步解码是如何进行的：
- 情况一：最后一个数字单独解码（即使用 s[i-1]）
  如果 s[i-1] 不是 '0'（'1' 到 '9'），那么这个数字可以单独解码成一个字母。此时，解码前 i 个字符的方法数就包含了解码前 i-1 个字符的所有方法，即 dp[i] += dp[i-1]。
- 情况二：最后两个数字组合解码（即使用 s[i-2] 和 s[i-1] 组成的两位数）
  这个两位数必须在 10 到 26 之间（包括 10 和 26）才能被有效解码。
  具体判断：令 num = int(s[i-2:i])（即取子串 s[i-2] 和 s[i-1] 组成的数字）。
  如果 10 <= num <= 26，那么这个两位数可以解码成一个字母。此时，解码前 i 个字符的方法数就包含了解码前 i-2 个字符的所有方法，即 dp[i] += dp[i-2]。
因此，状态转移方程为：
dp[i] = (如果 s[i-1] != '0' 则加上 dp[i-1]) + (如果 s[i-2] 和 s[i-1] 组成的两位数在 10~26 之间则加上 dp[i-2])
遍历顺序
从 i = 2 开始，一直计算到 i = n。因为每个状态 dp[i] 依赖于 dp[i-1] 和 dp[i-2]。
最终结果
dp[n] 就是整个字符串 s 的解码方法总数。

举例说明（以 s = "226" 为例）

n = 3。
初始化：dp[0] = 1。
i=1（第一个字符 '2'）: s[0] = '2' ≠ '0', 所以 dp[1] = 1。当前状态：[1, 1]
i=2（考虑前两个字符 "22"）:
- 情况一：最后一个数字 '2' 单独解码（有效），所以加上 dp[1] = 1。
- 情况二：最后两个数字 "22" 组成 22，在 10~26 之间（有效），所以加上 dp[0] = 1。
- dp[2] = 1 + 1 = 2。当前状态：[1, 1, 2]
- 解释：前两个字符 "22" 可以解码为 "BB" (2,2) 或者 "V" (22)。
i=3（考虑所有三个字符 "226"）:
- 情况一：最后一个数字 '6' 单独解码（有效），所以加上 dp[2] = 2。
- 情况二：最后两个数字 "26" 组成 26，在 10~26 之间（有效），所以加上 dp[1] = 1。
- dp[3] = 2 + 1 = 3。最终状态：[1, 1, 2, 3]
- 解释：对应题目描述中的三种解码方式。

边界情况与注意事项

如果字符串以 '0' 开头（如 "06"），则直接返回 0，因为无法解码。
在循环中，如果遇到 s[i-1] 是 '0'，且它前面的数字（s[i-2]）不是 '1' 或 '2'（即无法组成 10 或 20），那么整个字符串也无法解码，应返回 0。例如，s="100"，当 i=2 时，最后一个数字是 '0'，不能单独解码；看最后两位 "10"，是有效的，所以 dp[2] = dp[0] = 1。当 i=3 时，最后一个数字是 '0'，不能单独解码；看最后两位 "00"，是无效的（不在10~26）。此时 dp[3] 无法从任何有效路径转移，最终结果为 0。我们的算法通过判断条件自然处理了这种情况：在 i=3 时，情况一无效（s[2]=='0'），情况二无效（"00"不在10~26），所以 dp[3] 保持为 0。

这个动态规划解法的时间复杂度是 O(n)，空间复杂度通过状态压缩（只保留前两个状态）可以优化到 O(1)。

线性动态规划：解码方法题目描述一条包含字母 A-Z 的消息通过以下映射进行了编码： 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" 现在，给定一个只包含数字的非空字符串 s，请计算并返回解码方法的总数。题目数据保证答案肯定是一个 32 位的整数。示例 1 输入：s = "12" 输出：2 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。示例 2 输入：s = "226" 输出：3 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6)。示例 3 输入：s = "06" 输出：0 解释："06" 无法映射到 "F"，因为 "06" 不能视为 6。这是因为零不能单独存在，且数字不能以零开头。解题过程我们使用动态规划来解决这个问题。核心思想是：定义 dp[ i] 表示字符串 s 的前 i 个字符（即 s[ 0..i-1]）的解码方法数。我们需要找出 dp[ i ] 与之前状态的关系。定义状态设 dp[ i ] 表示前 i 个字符的解码方法总数。初始化基础情况 dp[ 0 ] = 1：空字符串有一种解码方式（可以将其视为解码的起点，一个合理的基准）。对于第一个字符（i=1）：如果 s[ 0 ] 是 '0'，则无法解码，直接返回 0。否则，dp[ 1 ] = 1。状态转移方程（核心）对于每个位置 i（从 2 到 n，n 为字符串长度），我们考虑最后一步解码是如何进行的：情况一：最后一个数字单独解码（即使用 s[ i-1]）如果 s[ i-1] 不是 '0'（'1' 到 '9'），那么这个数字可以单独解码成一个字母。此时，解码前 i 个字符的方法数就包含了解码前 i-1 个字符的所有方法，即 dp[i] += dp[i-1] 。情况二：最后两个数字组合解码（即使用 s[ i-2] 和 s[ i-1] 组成的两位数）这个两位数必须在 10 到 26 之间（包括 10 和 26）才能被有效解码。具体判断：令 num = int(s[i-2:i]) （即取子串 s[ i-2] 和 s[ i-1 ] 组成的数字）。如果 10 <= num <= 26 ，那么这个两位数可以解码成一个字母。此时，解码前 i 个字符的方法数就包含了解码前 i-2 个字符的所有方法，即 dp[i] += dp[i-2] 。因此，状态转移方程为： dp[i] = (如果 s[i-1] != '0' 则加上 dp[i-1]) + (如果 s[i-2] 和 s[i-1] 组成的两位数在 10~26 之间则加上 dp[i-2]) 遍历顺序从 i = 2 开始，一直计算到 i = n。因为每个状态 dp[ i] 依赖于 dp[ i-1] 和 dp[ i-2 ]。最终结果 dp[ n ] 就是整个字符串 s 的解码方法总数。举例说明（以 s = "226" 为例） n = 3。初始化：dp[ 0 ] = 1。 i=1（第一个字符 '2'）: s[ 0] = '2' ≠ '0', 所以 dp[ 1] = 1。当前状态：[ 1, 1 ] i=2（考虑前两个字符 "22"）: 情况一：最后一个数字 '2' 单独解码（有效），所以加上 dp[ 1 ] = 1。情况二：最后两个数字 "22" 组成 22，在 10~26 之间（有效），所以加上 dp[ 0 ] = 1。 dp[ 2] = 1 + 1 = 2。当前状态：[ 1, 1, 2 ] 解释：前两个字符 "22" 可以解码为 "BB" (2,2) 或者 "V" (22)。 i=3（考虑所有三个字符 "226"）: 情况一：最后一个数字 '6' 单独解码（有效），所以加上 dp[ 2 ] = 2。情况二：最后两个数字 "26" 组成 26，在 10~26 之间（有效），所以加上 dp[ 1 ] = 1。 dp[ 3] = 2 + 1 = 3。最终状态：[ 1, 1, 2, 3 ] 解释：对应题目描述中的三种解码方式。边界情况与注意事项如果字符串以 '0' 开头（如 "06"），则直接返回 0，因为无法解码。在循环中，如果遇到 s[ i-1] 是 '0'，且它前面的数字（s[ i-2]）不是 '1' 或 '2'（即无法组成 10 或 20），那么整个字符串也无法解码，应返回 0。例如，s="100"，当 i=2 时，最后一个数字是 '0'，不能单独解码；看最后两位 "10"，是有效的，所以 dp[ 2] = dp[ 0] = 1。当 i=3 时，最后一个数字是 '0'，不能单独解码；看最后两位 "00"，是无效的（不在10~26）。此时 dp[ 3] 无法从任何有效路径转移，最终结果为 0。我们的算法通过判断条件自然处理了这种情况：在 i=3 时，情况一无效（s[ 2]=='0'），情况二无效（"00"不在10~26），所以 dp[ 3 ] 保持为 0。这个动态规划解法的时间复杂度是 O(n)，空间复杂度通过状态压缩（只保留前两个状态）可以优化到 O(1)。