1. 题目链接：91. 解码方法
2. 题目描述：
一条包含字母
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只包含数字，并且可能包含前导零。
3. 算法思路：
1. 状态表示：
用i位置左结尾
2.状态转移方程：
关于i位置的编码情况，我们可以分为下面两种情况：
- 让
i位置上的数单独解码成一个字母 - 让
i位置上的数与i-1位置上的数结合，解码成一个字母
下面我们就上面的两种解码情况，继续分析：
-
让
i位置上的数单独解码成一个字母，就存在【解码成功】和【解码失败】两种情况 ：-
解码成功：当
i位置上的数在[1,9]之间的时候，说明i位置上的数是可以单独解码的，那么此时[0,i]区间上的解码方法应该等于[0,i-1]区间上的解码方法。因为[0,i-1]区间上的所有解码结果，后面填写一个i位置解码后的字母就可以了。此时dp[i]=dp[i-1] -
解码失败：当
i位置上的数是0的时候，说明i位置上的数是不能单独解码的，那么此时[0,i]区间上不存在解码方法。因为i位置如果单独参与解码，但是解码失败了，那么前面做的努力就白费了。此时dp[i]=0;
-
-
让
i位置上的数与i-1位置上的数结合在一起，解码成一个字母，也存在【解码成功】和【解码失败】两种情况：-
解码成功：当结合的数在
[10,26]之间的时候，说明[i-1,i]两个位置是可以解码成功的，那么此时[0,i]区间上的解码方法应该等于[0,i-2]区间上的解码方法，原因同上。此时dp[i]=d[i-2] -
解码失败：当结合的数在
[0,9]和[27,99]之间的时候，说明两个位置结合后解码失败（这里一定要注意00 01 02 03 04……这几种情况），那么此时[0,i]区间上的解码方法就不存在了，原因依旧同上，此时dp[i]=0
-
综上所述：dp[i]最终结果应该是上面四种情况下，解码成功的两种是累加和（因为我们关心的是解码方法，既然解码失败，就不用加入到最后结果中去），因此可以得到状态转移方程（dp[i]默认初始化为0）：
-
当
s[i]上的数在[1,9]区间时：dp[i]+=dp[i-1] -
当
s[i-1]与s[i]上的数结合后，在[10,26]之间的时候：dp[i]+=dp[i-2];
如果上述两个判断不成立，说明没有解码方法，d[i]就是默认值0
3. 初始化：
方法1（直接初始化）：
由于可能要用到i-1以及i-2位置上的dp值，因此要先初始化前两个位置
初始化dp[0]:
-
当
s[0]==‘0’时，没有编码成功，结果dp[0]=0 -
当
s[0]!=‘0’时，能编码成功，dp[0]=1
初始化dp[1]:
- 当
s[1]在[1,9]之间时，能单独编码，此时dp[1]+=dp[0]（原因同上，dp[1]默认为0） - 当
s[0]与s[1]结合后的数在[10,26]之间时，说明在前两个字符中，又有一种编码方式，此时dp[1]+=1
方法2（添加辅助位置初始化）：
可以在最前面加上一个辅助结点，帮助我们初始化，使用这种技巧要注意两个点：
辅助结点里面的值要保证后续填表正确
下标的映射关系
4. 填表顺序
从左往右
5. 返回值
应该返回dp[n-1]的值，表示在[0,n-1]区间上的编码方法
4. C++算法代码
class Solution {
public:int numDecodings(string s) {int n=s.size();//创建一个dp表vector<int> dp(n);//初始化前两个位置dp[0]=s[0]!='0';//说明dp[0]在1~9之间if(n==1) return dp[0];//处理边界情况if(s[1]<='9'&&s[1]>='1') dp[1]+=dp[0];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]<='9'&&s[i]>='1') 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];}
};
