题目：

题解：

1. 解法一：递归

很容易想到递归去解决，将大问题化作小问题。

比如 232232323232。

对于第一个字母我们有两种划分方式。

2|32232323232 和 23|2232323232

所以，如果我们分别知道了上边划分的右半部分 32232323232 的解码方式是 ans1 种，2232323232 的解码方式是 ans2 种，那么整体 232232323232 的解码方式就是 ans1 + ans2 种。可能一下子，有些反应不过来，可以看一下下边的类比。

假如从深圳到北京可以经过武汉和上海两条路，而从武汉到北京有 8 条路，从上海到北京有 6 条路。那么从深圳到北京就有 8 + 6 = 14 条路。

2. 解法二：递归 memoization

解法一的递归中，走完左子树，再走右子树会把一些已经算过的结果重新算，所以我们可以用 memoization 技术，就是算出一个结果很就保存，第二次算这个的时候直接拿出来就可以了。

3. 解法三：动态规划

同样的，递归就是压栈压栈压栈，出栈出栈出栈的过程，我们可以利用动态规划的思想，省略压栈的过程，直接从 bottom 到 top。

用一个 dp 数组， dp [ i ] 代表字符串 s [ i, s.len-1 ]，也就是 s 从 i 开始到结尾的字符串的解码方式。

这样和递归完全一样的递推式。

如果 s [ i ] 和 s [ i + 1 ] 组成的数字小于等于 26，那么

dp [ i ] = dp[ i + 1 ] + dp [ i + 2 ]

代码：

1. 代码一：（对应于解法一）


/** * code91 */
import java.util.*;

public class code91 {

    public static int numDecodings(String s) {
        return getAns(s, 0);
    }

    public static int getAns(String s, int start) {
        // 划分到了最后返回 1
        if (start == s.length()) {
            return 1;
        }

        // 若开头是 0, 则 0不对应任何字母，直接返回 0
        if (s.charAt(start) == '0') {
            return 0;
        }

        // 得到第一种的划分的解码方式
        int ans1 = getAns(s, start + 1);
        // 判断前两个数字是不是小于等于 26 的
        int ans2 = 0;
        if (start + 1 < s.length()) {
            int ten = (s.charAt(start) - '0') * 10;
            int one = s.charAt(start + 1) - '0';
            if (ten + one <= 26) {
                ans2 = getAns(s, start + 2);    // 得到第二种的划分的解码方式
            }
        }
        return ans1 + ans2;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = new String();

        while (sc.hasNextLine()) {
            str = sc.nextLine();
            int res = numDecodings(str);
            System.out.println(res);
            System.out.println("请继续进行输入：");
        }
    }
}

2. 代码二：（对应于解法二）

Map.getOrDefault(Object key, V defaultValue)方法的作用是：

当Map集合中有这个key时（key 已经存在），则返回该 key 对应的已存在的 value；
如果没有就使用默认值：defaultValue。


/** * code91 */
import java.util.*;

public class code91 {

    // 解法二：
    public static int numDecodings(String s) {
        HashMap<Integer, Integer> memoization = new HashMap<>();
        return getAns(s, 0, memoization);
    }

    public static int getAns(String s, int start, HashMap<Integer, Integer> memoization) {
        // 划分到了最后返回 1
        if (start == s.length()) {
            return 1;
        }

        // 若开头是 0, 则 0不对应任何字母，直接返回 0
        if (s.charAt(start) == '0') {
            return 0;
        }
        // 判断之前是否计算过
        int m = memoization.getOrDefault(start, -1);
        if (m != -1) // 如果之前计算过
        {
            return m;
        }

        // 得到第一种的划分的解码方式
        int ans1 = getAns(s, start + 1, memoization);
        // 判断前两个数字是不是小于等于 26 的
        int ans2 = 0;
        if (start + 1 < s.length()) {
            int ten = (s.charAt(start) - '0') * 10;
            int one = s.charAt(start + 1) - '0';
            if (ten + one <= 26) {
                ans2 = getAns(s, start + 2, memoization); // 得到第二种的划分的解码方式
            }
        }

        // 将结果保存
        memoization.put(start, ans1 + ans2);
        return ans1 + ans2;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = new String();

        while (sc.hasNextLine()) {
            str = sc.nextLine();
            int res = numDecodings(str);
            System.out.println(res);
            System.out.println("请继续进行输入：");
        }
    }
}

3. 代码三：（对应于解法三）


/** * code91 */
import java.util.*;

public class code91 {

    // 解法三：
    public static int numDecodings(String s) {
        int len = s.length();
        int dp[] = new int[len + 1];
        dp[len] = 1; // 将递归法的结束条件初始化为 1
        // 最后一个数字不等于 0, 就初始化为 1, 因为0 不代表任何字母
        if (s.charAt(len - 1) != '0') {
            dp[len - 1] = 1;
        }
        for (int i = len - 2; i >= 0; i--) // 当前数字为0时 ，直接跳过，因为0不代表任何字母
        {
            if (s.charAt(i) == '0') {
                continue;   //表面是continue,实际上dp[i]==0
            }
            int ans1 = dp[i + 1];
            // 判断两个字母组成的数字是否小于等于 26
            int ans2 = 0;
            int ten = (s.charAt(i) - '0') * 10;
            int one = s.charAt(i + 1) - '0';
            if (ten + one <= 26) {
                ans2 = dp[i + 2];
            }
            dp[i] = ans1 + ans2;
        }
        return dp[0];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = new String();

        while (sc.hasNextLine()) {
            str = sc.nextLine();
            int res = numDecodings(str);
            System.out.println(res);
            System.out.println("请继续进行输入：");
        }
    }
}

91. 解码方法

题目：

题解：