一条包含字母 A-Z 的消息通过以下方式进行了编码：
‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 给定一个只包含数字的非空字符串，请计算解码方法的总数。
题目数据保证答案肯定是一个 32 位的整数。
示例 1：
输入：“12” 输出：2 解释：它可以解码为 “AB”（1 2）或者 “L”（12）。 示例 2：
输入：“226” 输出：3 解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。 示例 3：
输入：s = “0” 输出：0 示例 4：
输入：s = “1” 输出：1 示例 5：
输入：s = “2” 输出：1
提示：
1 <= s.length <= 100 s 只包含数字，并且可以包含前导零。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/decode-ways 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：本题是动态规划的问题，首先找出子问题，要求数字串前N个字符的解密方式数，需要知道数字串前N-1和N-2个字符的解密方式数。 状态：设数字串S前i个数字解密成字母串有f[i]种方式。 转移方程： 初始条件：f[0] =1,即空串有1种方式解密，解密成空串。
class Solution { public: int numDecodings(string s) { int n = s.size(); if(n == 0) return 1; vector<int>f(n + 1,0); f[0] = 1;//初始条件 for(int i = 1;i <= n;++i) { if(s[i - 1] >= '1'&&s[i-1] <= '9') { f[i] = f[i-1];//解码方式没有增多 } //检查i大于1 即s至少要有两个 if(i > 1) { //s[i-2][i-1] int j = 10*(s[i-2] - '0')+(s[i - 1] - '0'); if(j >= 10&&j <= 26) f[i] += f[i-2];//当前用两个数字作为解码 再加上前面i-2个的解码总数 } } return f[n]; } };