算法:动态规划——解码方法问题

深思慎考

1025人浏览 · 2025-11-10 11:48:27

深思慎考 · 2025-11-10 11:48:27 发布

文章目录

从特殊到一般：动态规划破解解码方法问题

从特殊到一般：动态规划破解解码方法问题

题目回顾

在这里插入图片描述
题目链接
解码方法问题的核心是：给定仅含数字的非空字符串，按照 "1"→’A’ 到 "26"→’Z’ 的映射规则，计算有多少种合法的解码方式。关键约束包括：“0” 不能单独解码，“06” 这类以 0 开头的两位数不是合法编码，整个字符串必须完全解码（部分解码无效）。

例如 “11106” 有 2 种合法解码方式，而 “0”、“00”、“30” 等字符串的解码方法数为 0。

题解实现思路：从特殊情况切入，逐步构建通用逻辑

本题解采用 动态规划 思想，核心是通过 dp[i] 表示字符串前 i+1 个字符（即 s[0..i]）的合法解码总数。实现过程遵循 “先处理特殊情况，再推导通用递推” 的思路，确保逻辑严谨且无遗漏。

第一步：预处理 - 构建编码映射表

首先创建编码与字母的映射关系，用于快速判断某个数字串是否为合法编码：

unordered_map<string, char> mapping;
Solution() {
    for(int i = 1; i <= 26; i++) {
        mapping[to_string(i)] = 'A' + i - 1;
    }
}

配套的 exists 函数用于判断数字串是否在映射表中（即是否为合法编码）：

bool exists(string k) {
    return mapping.find(k) != mapping.end();
}

第二步：特殊情况前置判断（剪枝优化）

在开始动态规划前，先处理明显无法解码的特殊情况，直接返回结果以减少无效计算：

首字符为 ‘0’：由于 “0” 没有对应的编码，直接返回 0（如 “0”、“012”）；
字符串长度为 1：若首字符非 0，则只有 1 种解码方式（如 "5"→’E’），直接返回 1；
包含 “00” 子串：“00” 无法拆分为合法编码（既不能算 “0”+“0”，也不能算 “00”），直接返回 0（如 “100”、“2003”）。

这三步剪枝能快速处理边界案例，避免后续不必要的递推。

第三步：动态规划数组初始化

定义 dp 数组，dp[i] 表示 s[0..i] 的解码总数：

初始化 dp[0] = 1：前 1 个字符（非 0）只有 1 种解码方式。

第四步：分情况推导递推公式（核心逻辑）

从第 2 个字符（索引 i=1）开始，逐位遍历字符串，根据当前字符是否为 ‘0’ 分两大场景讨论，每个场景下再处理细分情况：

场景 1：当前字符 `s[i] != '0'`（可单独解码）

当前字符非 0 时，至少有 1 种解码方式（即当前字符单独解码，继承前 i-1 个字符的解码总数），再判断是否能与前一个字符组成合法的两位数编码：

子情况 1.1：前一个字符s[i-1] == ‘0’：前一个字符是 0，无法与当前字符组成两位数（如 “105” 中，“05” 不是合法编码），只能当前字符单独解码，因此dp[i] = dp[i-1]；
子情况 1.2：前一个字符非 0，且i-2 >= 0（存在dp[i-2]）：若s[i-1…i]是合法编码（如 "12"→’L’），则有两种解码方式：当前字符单独解码（dp[i-1]）+ 与前一个字符组合解码（dp[i-2]），因此dp[i] = dp[i-1] + dp[i-2]；
子情况 1.3：前一个字符非 0，但s[i-1…i]不是合法编码（如 “34”）：只能当前字符单独解码，因此dp[i] = dp[i-1]；
子情况 1.4：i-2 < 0（即i=1，字符串长度为 2）：若s[0…1]

是合法编码（如 “12”），则有 2 种解码方式（单独解码 + 组合解码），因此dp[i] = 2。

场景 2：当前字符 `s[i] == '0'`（不可单独解码）

‘0’ 不能单独解码，只能尝试与前一个字符组成两位数编码：

子情况 2.1：s[i-1…i]是合法编码（即前一个字符是 1 或 2，如 "10"→’J’、"20"→’T’）：组合解码后，解码总数继承前i-2个字符的解码总数（因为组合占了 2 个字符）。若i-2 >= 0，则dp[i] = dp[i-2]；若i=1（如 “10”），则dp[i] = 1（只有 1 种组合方式）；
子情况 2.2：s[i-1…i]不是合法编码（如 “30”、“00”）：无法解码，直接返回 0。

class Solution {
public:
    unordered_map<string, char> mapping;
    Solution()
    {
        for(int i = 1; i <= 26; i++)
        {
            mapping[to_string(i)] = 'A' + i-1;
        }
    }

    bool exists(string k)
    {
        if(mapping.find(k) != mapping.end())
        {
            return true;
        }
        return false;
    }

    int numDecodings(string s) 
    {
        int size = s.size();
        if(s[0] == '0')
            return 0;
        if(size == 1)
            return 1;
        if(s.find("00") != std::string::npos)
            return 0;
        
        vector<int> dp(size);
        dp[0] = 1;
        for(int i = 1; i < size; i++)
        {
            if(s[i] != '0')
            {
                if(s[i-1] == '0')
                    dp[i] = dp[i-1];
                else if(i-2 >= 0 && exists(s.substr(i-1, 2)))
                    dp[i] = dp[i-1] + dp[i-2];
                else if(!exists(s.substr(i-1, 2)))
                    dp[i] = dp[i-1];
                else if(i-2 < 0 && exists(s.substr(i-1, 2)))
                    dp[i] = 2;
                else
                    dp[i] = dp[i-1];

            }
            else
            {
                if(exists(s.substr(i-1, 2)))
                {
                    if(i-2 >= 0)
                        dp[i] = dp[i-2];
                    else
                        dp[i] = 1;
                }
                else
                    return 0;
            }
        }

        return dp[size-1];
    }
};

第五步：返回结果

遍历完成后，dp[size-1] 即为整个字符串的合法解码总数。

关键逻辑梳理（表格总结）

条件（当前字符 `s[i]`）	细分条件	递推公式	示例
非 ‘0’	前一个是 ‘0’	`dp[i] = dp[i-1]`	"105"→`dp[2] = dp[1] = 1`
非 ‘0’	前一个非 0，`s[i-1..i]` 合法，`i>=2`	`dp[i] = dp[i-1] + dp[i-2]`	"123"→`dp[2] = dp[1] + dp[0] = 2 + 1 = 3`
非 ‘0’	前一个非 0，`s[i-1..i]` 不合法	`dp[i] = dp[i-1]`	"135"→`dp[2] = dp[1] = 2`
非 ‘0’	`i=1`，`s[0..1]` 合法	`dp[i] = 2`	"12"→`dp[1] = 2`
‘0’	`s[i-1..i]` 合法	`dp[i] = dp[i-2]`（`i>=2`）或 1（`i=1`）	"120"→`dp[2] = dp[0] = 1`；"10"→`dp[1] = 1`
‘0’	`s[i-1..i]` 不合法	返回 0	"30"→直接返回 0