题目描述：

有一个消息包含A-Z通过以下规则编码

'A' -> 1'B' -> 2...'Z' -> 26

现在给你一个加密过后的消息，问有几种解码的方式

样例：

给你的消息为12，有两种方式解码 AB(12) 或者 L(12). 所以返回 2

算法分析：

'A'到'Z' 26个字母最多2位最少1位且不为0，因此存在多种解码的可能性。建立一维数组DP[i]表示到当前第i位字符时所能解码的方式，因此对于某一位i，若其不为‘0’，则DP[i] += DP[i-1],若其能与i-1位构成的数字在1到26之间，则DP[i]+=DP[i-2]。因此动态规划表达式为：

　　　　①S[i]!=0：DP[i] = DP[i-1] + (S[i-1]=='1'||S[i-1]=='2'&&S[i]<='6')?DP[i-2]:0；

　　　　②S[i]=0：DP[i] = (S[i-1]=='1'||S[i-1]=='2')?DP[i-1]:0；

要注意的一点是在进行二位数判断时直接用字符进行判断即可，Integer.valueOf()反而会增加代码量如对前一位是‘0’的处理等等；

代码：

public class Solution {    /*     * @param s: a string,  encoded message     * @return: an integer, the number of ways decoding     */    public int numDecodings(String s) {        // write your code here        int length = s.length();        //对首位0或空字符串进行处理        if(length==0||s.charAt(0)=='0'){            return 0;        }        int[] result = new int[length+1];        result[0] = 1;        result[1] = 1;        for(int i=1;i