解码方法
难度：中等
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1 'B' -> 2 ... 'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12" 输出: 2 解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:
输入: "226" 输出: 3 解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
题目分析：
做完之后才知道，这题为啥通过率这么低。这个0是真的恶心。1.当0和前面的数组合大于26时就无效返回0；2.当连续出现0的时候无效返回0；3.当0和出现在首位的时候无效，返回0.这题显然用DP。
1.状态转换方程是f[i] = f[i-1] + f[i-2] (在当前值和前面一个值组合小于等于26的时候);
f[i] = f[i-1] (当前值和前面一个值组合大于26时)
f[i] = f[i-1] (前面一个值为0的时候)
2.数据结构选择一维数组
3.初始化，注意0可能出现在第一和第二位。当没有0出现时，f[0] = 1,f[1]和f[0]的组合大于等于26时，f[1] = 1,否则 f[1] =2;
4,遍历填表。很关键的是要分析0的情况（具体见代码）
参考代码：
class Solution {
public:int numDecodings(string s) {if (s.empty())return s.size();vector<int> f;f.resize(s.size());//首位为0，返回0；否则初始化if (s[0] == '0')return 0;elsef[0] = 1;//必须要判断，否则如果只有一位，下面的s[1]会越界if (s.size() == 1)return 1;//第二位不为0，如果和s[0]组合小于等于26，f[1] = 2,否则f[1] = 1//第二位为0，如果前面那位大于2，就是无效数组，返回0if (s[1] != '0' && (s[0] - '0') * 10 + s[1] - '0' <= 26)f[1] = 2;else if (s[1] == '0' && !(s[0] == '1' || s[0] == '2'))return 0;elsef[1] = 1;int temp = 0;//从第三个数开始遍历,大致分三种情况for (int i = 2; i < s.size(); i++){//当前值为0，前面的值为1或者2，有效，当前的总数等于前面第二位if (s[i] == '0' && (s[i - 1] == '1' || s[i - 1] == '2'))f[i] = f[i - 2];//当前值为0，前面的值不为1或者2，无效else if (s[i] == '0' && !(s[i - 1] == '1' || s[i - 1] == '2'))return 0;//当前值不为0的情况，需要判断前面那个值为不为0else if (s[i] > '0' && s[i] <= '9'){//前面的值不为0，正常判断if (s[i - 1] != '0'){temp = (s[i - 1] - '0') * 10 + s[i] - '0';if (temp <= 26)f[i] = f[i - 1] + f[i - 2];elsef[i] = f[i - 1];}else{//前面的值为0，当前的总数等于前面第二位f[i] = f[i - 2];}}}return f[s.size() - 1];}
};