https://leetcode-cn.com/problems/decode-ways/

动态规划

从左到右的尝试模型

 public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        return process(str, 0);
    }
    // 潜台词：str[0...index-1]已经转化完了，不用操心了
    // str[index....] 能转出多少有效的，返回方法数
    private int process(char[] str, int index) {
        if (index == str.length) {
            return 1;
        }
        if (str[index] == '0') {
            return 0;
        }
        int ways = process(str, index + 1);
        if (index + 1 == str.length) {
            return ways;
        }
        int num = (str[index] - '0') * 10 + (str[index + 1] - '0');
        if (num <= 26) {
            ways += process(str, index + 2);
        }
        return ways;
    }

// 动态规划
    public int numDecodings2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int N = s.length();
        int[] dp = new int[N + 1];
        char[] str = s.toCharArray();
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            if (str[i] != '0') {
                dp[i] = dp[i + 1];
                if (i + 1 == str.length) {
                    continue;
                } else {
                    int num = (str[i] - '0') * 10 + (str[i + 1] - '0');
                    if (num <= 26) {
                        dp[i] += dp[i + 2];
                    }
                }
            }
        }
        return dp[0];
    }