題目

解碼方法
非常明顯，遞歸可以做，可能會爆棧，最佳方法是DP。
求狀態(tài)轉(zhuǎn)移方程。
首先考慮最后一個數(shù)字的解碼方式。以f[i]表示前 i個字符串的解碼方式總數(shù)。如果選擇一個數(shù)字，此時的解碼方式數(shù)就是:f_i=f_i-1, 當(dāng)然 s[i-1]不能是字符0。
如果選擇兩個字符進行解碼， 此時解碼方式數(shù)是：f_i=f_i-2。此時i >= 2, s[i-2]不能是字符0，而且s[i-2]和s[i-1]組成的數(shù)字介于1～26。
所以最終的解碼方式數(shù)應(yīng)該是這兩部分的相加。
dp[0]應(yīng)該是什么呢？"" 有幾種解碼方式？ 1=> 仍然是空字符串
程序基本框架就是：

dp size -> s.length + 1
dp[0] = 1
i from 1 to dp.size
    if s[i-1] != '0'
        dp[i] += dp[i-1]
    if i>=2 and s[i-2] != '0' and (10*s[i-2]+s[i-1]) <= 26
        dp[i] += dp[i-2]
ans = dp[i]
    

數(shù)組版本代碼

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

時間復(fù)雜度：O（n+1-1）=> O(n)
空間復(fù)雜度：O（n+1）=> O(n)

向后計算時，dp數(shù)組前面的元素已經(jīng)被丟棄了，實際使用的只有最近的兩個元素。和斐波納切數(shù)列很像。

class Solution {
    public int numDecodings(String s) {
        int length = s.length();
        int fn_1 = 1;
        int fn_2 = 0;
        int fn = 0;
        for(int i = 1;i <= length;i++){
            fn = 0;
            if(s.charAt(i-1) != '0'){
                fn += fn_1;
            }
            if(i >= 2 && s.charAt(i-2) != '0' && (10*(s.charAt(i-2)-'0')+s.charAt(i-1)-'0') <= 26 && (10*(s.charAt(i-2)-'0')+s.charAt(i-1)-'0' > 0)){
               fn += fn_2; 
            }
            fn_2 = fn_1;
            fn_1 = fn;
        }
        return fn;
    }
}

時間復(fù)雜度： O(n)
空間復(fù)雜度： O(1)