【动态规划：斐波那契数列模型】解码方法

91. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1 1 10 6)
• "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 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" ，因为存在前导零（"6" 和 "06" 并不等价）。

提示：

• 1 <= s.length <= 100
• s 只包含数字，并且可能包含前导零。

---

解题思路

​ 下图中给出了动态规划表的状态表示，还有状态转移方程：

​ 值得注意的是，要具体编码的时候，s[i] 和 s[i-1] 一起解码这种情况中 10 <= a*10 + b <= 26，其中 a 和 b 是字符，所以 必须让它们都减去 ‘0’ 才能得到对应的数字大小，这个要注意，它们并不是个位数字本身！

​ 还有就是为什么不讨论 s[i+1] 和 s[i] 解码的情况呢❓❓❓这是因为我们 dp[i] 表示的是从头到 i 位置处的解码方法总数，所以当然不用考虑 i 后面的字符情况！

​ 现在来讨论一下初始化的问题，因为我们是从左向右推导，并且涉及到 dp[i-2] 和 dp[i-1]，那么势必要将前两个元素进行初始化。

​ 下面还是用图片的形式来给出初始化的问题：

class Solution {
public:int numDecodings(string s) {// 创建dp表，dp[i]：以i结尾时的解法总数int n = s.size();vector<int> dp(n);// 初始化dp[0]和dp[1]，因为状态转移方程需要借助到i-1和i-2if(s[0] != '0')dp[0] = 1;if(n == 1)return dp[0]; // 处理一下边界问题，因为题目范围从1个字符开始if(s[1] != '0' && s[0] != '0') // 单独编码的情况dp[1]++;int tmp = s[1]-'0' + (s[0]-'0')*10; // 合起来编码的情况if(tmp >= 10 && tmp <= 26) dp[1]++;// 填表for(int i = 2; i < n; ++i){if(s[i] != '0') // 单独编码的情况dp[i] += dp[i - 1];// 合起来编码的情况tmp = s[i]-'0' + (s[i - 1]-'0')*10;if(tmp >= 10 && tmp <= 26)dp[i] += dp[i - 2];}return dp[n - 1];}
};

优化

​ 与其说是优化，不如说是处理边界问题以及初始化问题的技巧！

​ 从上面这段代码可以发现，其实这个 dp[1] 和我们在 for 循环中判断是一模一样的，只不过 dp[1] 变成了 dp[i]，仅此而已。那么这样子冗余的代码其实是不太好看的，写起来也是非常别扭，所以我们来将其优化一下！

​ 其实思路很简单，既然 dp[1] 的判断和后面是一样的，而只有 dp[0] 是需要单独拎出来做额外判断的，那么我们就 先多给 dp 表一个空间，然后将整体往后移动一位，并且将新的 dp[0] 作为虚拟位来填充，如下图所示：

class Solution {
public:int numDecodings(string s) {// 优化int n = s.size();vector<int> dp(n + 1); // 多开一个空间dp[0] = 1; // 第一位是虚拟位，为了保证第三个字符填表时的正确，这里填1，注意不能为0if(s[0] != '0') // dp[1]相当于原来的dp[0]dp[1] = 1;// 填表，注意是遍历到n，并且原来的关于s的下标都要再减一，因为dp表全体往后移动了一位for(int i = 2; i <= n; ++i){if(s[i - 1] != '0') // 单独编码的情况dp[i] += dp[i - 1];// 合起来编码的情况int tmp = s[i - 1]-'0' + (s[i - 2]-'0')*10;if(tmp >= 10 && tmp <= 26)dp[i] += dp[i - 2];}return dp[n];}
};