题目描述：
一条包含字母 A-Z 的消息通过以下方式进行了编码：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1：
输入：s = “226”
输出：3
解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
示例 2：
输入：s = “0”
输出：0
分析：
因为 s[0:i] 的解码方案 可以由 s[0:i-1] 的解码方案 和 s[i] 的值推导得到
所以 可以使用动态规划算法解决。下面具体分析：
给定 数字字符串 “1226” ，去掉最后一位得到子串 “122” ，”122″ 可解码
为 1,2,2 12,2 1,22 三种，”1226″的解码方案 是将字符 ‘6’ 加到 “122”的所有解码方案中
对1，2，2 生成”1226″的解码序列 有两种选择，’6′ 单独作一位加在后面 1，2，2，6
或 ‘6’ 和 最后一位2拼接成 1，2，26 。由 “122”的解码方案 生成 “1226”的解码方案有
1，2，2，6 1，2，26 12，2，6 12，26 1，22，6
即可以根据 s[0:i-1] 的解码方案 和 s[i] 的值推出 s[0:i] 的解码方案。需要特别考虑 s[i-1] 和 s[i] 为 ‘0’ 的情况。
1. 定义状态 dp[i] ：s[0 : i] 的所有解码， np[i] s[0 : i] 的所有解码中，最后一个编码是1位的解码，如 对 “122”
的解码 1,2,2 12,2 1,22 dp[2] = 3 ，np[2] = 2 。
状态转移和 状态空间压缩 见下面代码和注释：
1 class Solution {
2 public:
3 int numDecodings(string s)
4 {
5 int dp ;
6 int np ;
7 //base case
8 if(s[0] == '0'){
9 dp = 0;
10 np = 0;
11 }
12 else
13 {
14 dp = 1;
15 np = 1;
16 }
17 //state move
18 for(int i = 1;i < s.size();++i)
19 {
20 if(s[i-1] == '0')//s[0:i-1] 有效的结尾只可能是 10，20，
21 {
22 if(s[i] == '0') //‘0’ 既不能拼接在 10，20 后面，也 单独作一位
23 {
24 dp = 0;
25 np = 0;
26 }
27 //非‘0’ 可以单独作一位
28 else
29 {
30 if(dp > 0)//单独作一位跟在 ‘10’ ‘20’ 后面
31 {
32 // dp = dp;
33 np = dp;
34 }
35 else//s[0:i-1] 没有合法的解码方法
36 {
37 dp = 0;
38 np = 0;
39 }
40 }
41 }
42 else if(s[i] == '0') // s[i-1] ！= '0' ，s[i] == '0'
43 // s[i] == '0' 只能在 s[i-1]是 1或2 的时候与之拼接成‘10’或’20‘，不能在其他情况下拼接，也不能单独作一位
44 {
45 if(s[i-1] == '1' || s[i-1] == '2') //s[i-1]是 1或2 的时候与之拼接成‘10’或’20‘
46 {
47 dp = np;
48 np = 0;
49 }
50 else
51 {
52 dp = 0;
53 np = 0;
54 }
55 }
56 //s[i]和s[0:i-1]的所有解码序列 即可拼接又可单独作一位
57 else if(s[i-1] == '1' || (s[i-1] == '2' && s[i] >= '1' && s[i] <= '6'))
58 {
59 int temp = dp;
60 dp = dp + np;
61 np = np + (temp - np);
62 }
63 // s[i-1] 不是 0，1，2 s[i] 不是0，s[i]只能单独作一位
64 else
65 {//dp 不变 所有的s[0:i-1]的 2位结尾的解码，全部都变成 1位结尾的解码，1位结尾的解码依然是一位结尾的解码
66 // dp = dp;
67 np = dp;
68 }
69 }
70 return dp;
71 }
72 };
