一条包含字母A-Z的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
....
'Z' -> 26
给定一个只包含数字（包括0）的非空字符串，请计算解码方法的总数。
示例1：
输入：“12”
输出：2
解释：它可以解码为“AB”（1 2）或者“L”（12）
示例2：
输入：“226”
输出：3
解释：它可以解码为“BZ”（2 26），“VF”（22 6），或者“BBF”（2 2 6）
解题思路（动态规划） 首先举例子：例如计算22113的解码方法数量（从左往右）
- 2有一种
- 22有两种（2 2）（22）
- 223有三种（2 2 3）（22 3）（2 23）
- 2211有五种（2 2 1 1）（22 1 1）（2 21 1）（2 2 11）（22 11）
- 22113有八种（2 2 1 1 3）（22 1 1 3）（2 21 1 3）（2 2 11 3）（2 2 1 13）（22 11 3）（2 21 13）（22 1 13） 咦，好像发现了什么，对了，就是斐波那契！
但是如果碰见0的情况呢。
例如：02，909，这些情况结果都为0。
也就是说，状态转移方程不是单纯的f[i]=f[i-1]+f[i-2];
解法如下：
首先，建立dp数组，长度比输入字符串大1，dp[i]表示输入字符串中的开始位到i-1位的字串的解法数量。
1.首先判断第i位，检查是否为‘0’，若是则将dp[i]赋值为0，如不是，则dp[i]=dp[i-1];
2.再判断第i位和i-1位，检查该两位是否小于“26”，如果小于，则dp+=dp[i-2];否则不操作。
3.遍历完后返回dp[dp.length-1];
再用22113为例，在对最后一位分析时，numDecodings("22113") = numDecodings("2211")+numDecodings("221")
代码如下：
public int numDecodings(String s) {
if(s == null || s.charAt(0)=='0'){
return 0;
}
int[] dp = new int[s.length()+1];
dp[0] = 1;
for(int i = 1; i < dp.length; i++){
dp[i] = (s.charAt(i-1)=='0'?0:dp[i-1]);
if(i >= 2 && (s.charAt(i-2) == '1' || (s.charAt(i-2) == '2' && s.charAt(i-1) <= '6'))){
dp[i] += dp[i-2];
}
}
return dp[dp.length-1];
}
