题目来源
本题来源为：
题目描述
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：
注意，消息不能分组为 (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];
}
};