动态规划43（Leetcode91解码方法）

代码：

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(s.charAt(0)=='0')return 0;
        if(n==1)return 1;
        int[] dp = new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            if(s.charAt(i-2)=='1'){
                dp[i]+=dp[i-2];
            }else if(s.charAt(i-2)=='2'&&s.charAt(i-1)>='0'&&s.charAt(i-1)<='6'){
                dp[i]+=dp[i-2];
            }
            if(s.charAt(i-1)!='0'){
                dp[i]+=dp[i-1];
            }
        }
        return dp[n];
    }
}