這個題不算是一個常規(guī)套路的題踪栋，我們需要分析一下

假設(shè)我們要求的數(shù)是2荷愕，其方式顯然只有一種

假設(shè)我們要求的數(shù)是22
1.由 null + 22組成
2.由2 + 2組成
這個地方有一點(diǎn)需要注意涛舍，加號后的數(shù)應(yīng)被看作為一個整體，是不可拆分的。也就是說，這里的22不能被拆分
加號前的數(shù)是已經(jīng)計算過的人芽，直接取值就可以，也不需要再去拆分

假設(shè)我們要求的數(shù)是226
1.由null + 226組成（這是不可能的绩脆，因?yàn)槿≈捣秶?-26）
2.由2 + 26組成（可以看到2和26我們之前都計算過了）
3.由22 + 6組成（可以看到22和6我們之前都計算過了）

現(xiàn)在我們可以歸納出動態(tài)方程了 當(dāng)前的解碼方法數(shù) = 去掉前一位的解碼方法書 + 去掉前兩位的解碼方法數(shù)
dp[i] = dp[i - 1] + dp[i - 2]
dp[0] = 1 拆分成null和自身 null的方法數(shù)為1
dp[1] = 1

除此之外 我們還需要考慮0的問題萤厅，具體見代碼

class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        /** 處理0 */
        //如果有兩0相連 肯定不行
        for (int i = 1; i < len; i ++) {
            if (s.charAt(i - 1) == '0' && s.charAt(i) == '0')
                return 0;
        }
        //如果開頭是0肯定不行
        if (s.charAt(0) == '0')
            return 0;
        //若果結(jié)尾是0 則只剩一種情況

        int[] dp = new int[len + 1];
        //當(dāng)前字符串s可能是從 s - 2 或 s - 1 添加一位或者兩位數(shù)得到的(1-26 只能添加1位或者2位 不可能添加0位或者三位及以上)
        //dp[i] = dp[i - 2] + dp[i - 1]

        /** base case */
        dp[0] = 1; // dp[0]代表分解成null和整體 22可以分解成 2 + 2 或者 null + 22
        dp[1] = 1;

        /** dp i代表幾個字符 即s[i - 1]個字符 */
        for (int i = 2; i <= len; i ++) {
            if (Integer.parseInt(s.substring(i - 2,i)) > 26 || s.charAt(i - 2) == '0') { //如果最后兩位是>26的 或倒數(shù)第二位是0 那么這個s只能由s - 1加一位組成
                if (s.charAt(i - 1) == '0') //如果果結(jié)尾是0 則s-1的情況也無法滿足
                    return 0;
                else
                    dp[i] = dp[i - 1];
            }
            else {
                if (s.charAt(i - 1) == '0') //如果果結(jié)尾是0 則s-1的情況無法滿足
                    dp[i] = dp[i - 2];
                else
                    dp[i] = dp[i - 2] + dp[i - 1];
            }
        }

        return dp[len];
    }

}