【动态规划：斐波那契数列模型】解码方法
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 <= 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]; }};
