Decode Ways

public class Solution {
    public int numDecodings(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (s.length() == 0)
            return s.length();
        else if (s.startsWith("0"))
            return 0;
        else if (s.length() == 1){
            return 1;
        }
        
        else {
            int sum = 0; 
            int temp = Integer.parseInt(s.substring(0,2));
            if (temp <= 26 && temp > 0)
                if (s.length() > 2)
                    sum += numDecodings(s.substring(2, s.length()));
                else
                    sum += 1;
            sum += numDecodings(s.substring(1, s.length()));
            return sum;
        }
    }
}

递归的方法，就是需要注意0开头的字符串是不能被parse的。但是。。。。大数据超时了？？唉。。。
看了代码，发现确实有这个问题，numDecodings(s.substring(1, s.length()))还会重复计算之前计算过的numDecodings(s.substring(2, s.length()))
那么只能逆着递推了(类似动规？)

public class Solution {
    public int numDecodings(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int length = s.length();
        if (length == 0)
            return 0;
        int[] count = new int[length+1];
        count[length] = 1;
        if (s.charAt(length-1) =='0')
            count[length-1] = 0;
        else
            count[length-1] = 1;
        for (int i = length-2; i >=0; --i){
            if (s.charAt(i) != '0')
                count[i] += count[i+1];
            else
                continue;
            int temp = Integer.parseInt(s.substring(i,i+2));
            if (temp <=26)
                count[i] += count[i+2];
        }
        return count[0];
    }
}