力扣91. 解码方法(两种解决方案 -递归DFS - 动态规划)

示例 1：
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）

示例 2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：
输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

题意：

这里每一个数字都对应一个字符，如果是两个数字的话必须小于等于26才能对应一个字符，如果数字是0的话，那么就不能组成字符。

首先想到的是DFS，把字符串不停的拆开，可以拆成一个字符，也可以拆成两个字符。可以利用二叉树来直观的展示：

通过上图可知，可以利用一个index下标，来进行拆分。如果index >=字符串的长度了，那么就说明整个字符串拆分结束，结果就加1了。一旦遇到0的情况，就返回。

通过观察上图可知，有许多重复的计算，如下图所示，比如两个红色框内都只剩下205。

所以这个时候为了减少重复计算，我们可以优化一下，把计算过的结果存储起来，下次
运算的时候判断有没有计算过，如果计算过就不用再重复计算，看下代码

class Solution {
    public int numDecodings(String s) {
        int[] map = new int[s.length() + 1];
        Arrays.fill(map,-1);
        return findsum(s,s.length() , 0 ,map);
    }
    public int findsum(String s ,int length ,int i ,int[] map){
        if(i >= length){
            return 1;
        }
        if(s.charAt(i) == '0'){
            return 0;
        }
        if(map[i] != -1){
            return map[i];
        }
        int res = findsum(s,length,i +1,map);
        if(i < length - 1 && (s.charAt(i) == '1'  || (s.charAt(i) == '2' && s.charAt(i + 1) <='6'))){
            res += findsum(s,length , i+2,map);
        }
        map[i] = res;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

递归解法

递归是从下到上开始计算，他是一直蒙着头往下走，当走到叶子节点的时候在回去。实
际上我们还可以从上到下来计算，也就是这里讲的动态规划。

定义dp[i]表示前i个字符的解码数。

如果求前i个字符的解码数

1 .我们可以通过先求前 i- 1 个字符的解码数，但前提条件是当前字符也是可以解码的

2 我们可以求 i- 2 个字符的解码数，但前提条件是当前字符和前一个字符构成的两个数字是有效的，也就是小于等于26

每次截取一个或者每次截取两个，看到这里大家应该已经明白了，如果没有条件限制的
话，这题解法和356，青蛙跳台阶相关问题完全一样，每次跳一个台阶或者每次跳两个
台阶，递归公式其实就是个斐波那契数列
dp[i]=dp[i-1]+dp[i-2]

只不过这里的斐波那契数列是有条件的，需要根据根据条件判断哪一项该加，哪一项不
该加，但原理都差不多，来看下代码

class Solution {
    public int numDecodings(String s) {
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for(int i = 1; i <= s.length() ; i++){
            if(s.charAt(i -1 ) != '0'){
                dp[i] = dp[i-1];
            }
            if(i >= 2 && (s.charAt(i-2) == '1' || (s.charAt(i-2) == '2' && s.charAt(i-1)<= '6'))){
                dp[i] += dp[i-2];
            }
        }
        return dp[s.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15