【动态规划：斐波那契数列模型】解码方法
【动态规划：斐波那契数列模型】解码方法
一条包含字母 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 <= 100s只包含数字，并且可能包含前导零。
解题思路
下图中给出了动态规划表的状态表示，还有状态转移方程：
值得注意的是，要具体编码的时候，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-2
if(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，注意不能为0
if(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];
}
};腾讯云开发者
