解码方法

一条包含字母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.length <= 100
• s只包含数字，并且可能包含前导零。

91.编码方法

有人相爱，有人夜里看海，有人一道动态规划死活写不出来

对于一个字符串，编码出的最后一个字母可以是根据字符串最后一个字符，也可以是根据字符串最后两个字符。如果是根据最后一个字符进行编码的，那么该字符不能为’0’，如果是根据最后两个字符编码的，那么不能有前导0且不大于26。

根据以上推算，容易得到动态方程。既然那么容易，我就不写了

要注意的是，长度为1和2时对字符串的判断。如果长度为1，那么直接判断是不是’0’就好了，如果长度为2，判断最后两个字符可以编码时，是要给当前dp值加一，而不是加上之前第二个的dp值，否则会越界。

感觉没说清楚，反正就是会越界，看代码就知道了

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n, 0);
        dp[0] = (s[0] != '0');
        for(int i = 1; i < n; ++i){
            if(s[i] != '0'){
                dp[i] += dp[i - 1];
            }
            if(i > 0 && s[i - 1] != '0' && 10 * (s[i - 1] - '0') + (s[i] - '0') <= 26){
                dp[i] += (i > 1 ? dp[i - 2] : 1);
            }
        }
        return dp[n - 1];
    }
};

官方题解中，给dp加了个头，就不用考虑前面说的越界问题，但是dp的意义会变，要变下标。

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for(int i = 0; i < n; ++i){
            if(s[i] != '0'){
                dp[i + 1] += dp[i];
            }
            if(i > 0 && s[i - 1] != '0' && 10 * (s[i - 1] - '0') + (s[i] - '0') <= 26){
                dp[i + 1] += dp[i - 1];
            }
        }
        return dp[n];
    }
};