91. Decode Ways

这道题和普通的DP题不太一样，用的是top-down的方法。
也就是从n开始，而不是从0开始建表。
注意dp[ ]的size，比string s多1。
base case ：dp[n] = 1; dp[n-1] = 0 or 1;
时间O(n)，空间也是O(n);

public class Solution {
    public int numDecodings(String s) {
        if(s == null || s.length()==0)  return 0;
        int n = s.length();
        
        int dp[] = new int[n+1];
        dp[n] = 1;
        dp[n-1] = s.charAt(n-1)=='0'? 0:1;
        
        for(int i=n-2; i>=0; i--) {
            if(s.charAt(i) != '0')
                dp[i] = (Integer.parseInt(s.substring(i,i+2)) <= 26) ? dp[i+1] + dp[i+2] : dp[i+1];
        }
        return dp[0];
    }
}