题目来源
本题来源为：
题目描述
一条包含字母 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 位 的整数
题目解析
解码按照规则解码即可，但是前导0不可解码。
算法原理
1.状态表示
经验+题目要求：
以i位置为结尾…
对于本题而言就是：
dp[i]表示：以i位置为结尾时，解码方法的总数
2.状态转移方程
在推方程之前，我们先画一下解码的情况：
分为单独解码和与前一个位置一起解码两种情况：
而单独解码和一起解码又要分为两种情况，成功和失败。
为什么会失败呢？
举个例子：
2和5可以一起解码，也可以分开解码，但到0位置时，就会解码错误，自己单独不能解码，要是与后面的6结合，
会出现之前说的前导0情况，也会解码错误。
因此，本题的状态转移方程为：
dp[i] = dp[i-1]+ dp[i-2]
3.初始化
本题初始化要在下标为0位置与下标为1位置进行初始化：
dp[0]=s[0]!='0'; //处理边界条件： if(n==1) return dp[0]; if(s[0]!='0'&&s[1]!='0') dp[1]+=1; //前两个位置所表示的数： int t=(s[0]-'0')*10+s[1]-'0'; if(t>=10&&t<=26) dp[1]+=1;
4.填表顺序
根据状态转移方程，我们计算dp[i]位置的值需要i-1与i-2位置的值，因此我们的填表顺序为：从左往右
5.返回值
我们要解码到最后一个位置，因此：返回dp[n-1]
代码实现
class Solution { public: int numDecodings(string s) { // 1.创建dp表 // 2.初始化 // 3.填表 // 4.返回值 int n=s.size(); vector<int> dp(n); dp[0]=s[0]!='0'; //处理边界条件： if(n==1) return dp[0]; if(s[0]!='0' && s[1]!='0') dp[1]+=1; //前两个位置所表示的数： int t=(s[0]-'0')*10+s[1]-'0'; if(t>=10&&t<=26) dp[1]+=1; for(int i=2;i<n;i++) { //处理单独编码： if(s[i]!='0') dp[i]+=dp[i-1]; //第二种情况对应的数： int t=(s[i-1]-'0')*10+s[i]-'0'; if(t>=10&&t<=26) dp[i]+=dp[i-2]; } return dp[n-1]; } };
