這道題和普通的DP題不太一樣紧唱，用的是top-down的方法抵拘。
也就是從n開始，而不是從0開始建表寝杖。
注意dp[ ]的size，比string s多1互纯。
base case ：dp[n] = 1; dp[n-1] = 0 or 1;
時(shí)間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];
}
}
