【动态规划】【斐波那契数列模型】解码方法

解码方法

91. 解码方法

算法原理

1. 确定状态表示
   • 经验+题目要求：
   • 以 i 位置为结尾
   • dp[i] 表示以 i 位置为结尾时，解码方法的总数
2. 状态转移方程

定义好状态表示，我们就可以分析 i 位置的 dp 值，如何由 [前面] 或者 [后面] 的信息推导出来。关于 i 位置的编码状况，我们可以分为下面两种情况：

1. 让 i 位置上的数单独解码成一个字母
2. 让 i 位置上的数与 i-1 位置上的数结合，解码成一个字母

下面我们就上面的两种解码情况，继续分析：

• 让 i 位置上的数单独解码成一个字母，就存在 [解码成功] 和 [解码失败] 两种情况：
  1. 解码成功：当 i 位置上的数在 [1, 9] 之间的时候，说明 i 位置上的数是可以单独解码的，那么此时 [0, i] 区间上的解码方法应该等于 [0, i-1] 区间上的解码方法。因此 [0, i-1] 区间上的所有解码结果，后面填上一个 i 位置解码后的字母就可以了。此时 dp[i] = dp[i-1]
  2. 解码失败：当 i 位置上的数是 0 的时候，说明 i 位置上的数是不能单独解码的，那么此时 [0, i] 区间上不存在解码方法。因为 i 位置如果单独参与解码，但是解码失败了，那么前面做的努力就全部白费了。此时 dp[i] = 0
• 让 i 位置上的数与 i-1 位置上的数结合在一起，解码成一个字母，也存在 [解码成功] 和 [解码失败] 两种情况：
  1. 解码成功：当结合的数在 [10, 26] 之间的时候，说明 [i-1, i] 两个位置是可以解码成功的，那么此时 [0, i] 区间上的解码方法应该等于 [0, i-2] 区间上的解码方法，原因同上。此时 dp[i] = dp[i-2]
  2. 解码失败：当结合的数在 [0, 9] 和 [27, 99] 之间的时候，说明两个位置结合后解码失败（这里一定要注意 00，01，02，03… 这几种情况），那么此时 [0, i] 区间上的解码方法就不存在了，原因依旧同上。此时 dp[i] = 0

综上所述：dp[i] 最终的结果应该是上面四种情况下，解码成功的来那个中的累加和（因为我们关心的是解码方法，既然解码失败，就不用加入到最终的结果中去），因此可以得到状态转移方差（dp[i] 默认初始化为 0）

1. 当 s[i] 上的数在 [1, 9] 区间上时：dp[i] = dp[i-1]
2. 当 s[i-1] 与 s[i] 上的数结合之后，在 [10, 26] 之间的时候：dp[i] += dp[i-2] 如果上述两个判断都不成立，说明没有解码方法，dp[i] 就是默认值 0
3. 初始化 由于可能要用到 i-1 以及 i-2 的位置上的 dp 值，因此要先初始化 [前两个位置]

初始化 dp[0]：

1. 当 s[0] == ‘0’ 时，没有编码方法，结果 dp[0] = 0
2. 当 s[0] != '0' 时，能编码成功，dp[0] = 1

初始化 dp[1]

1. 当 s[1] 在 [1, 9] 之间时，能单独编码，此时 dp[1] += dp[0]（原因同上，dp[1] 默认为 0）
2. 当 s[0] 与 s[1] 结合后的数在 [10, 26] 之间时，说明在前两个字符中，又有一种编码方式，此时 dp[1] += 1
3. 填表顺序
   • 毫无疑问，是从左往右
4. 返回值
   • 应该返回 dp[n-1] 的值，表示在 [0, n-1] 区间上的

代码编写

public int numDecodings(String ss) {  
    //1. 创建 dp 表（看返回值）  
    int n = ss.length();  
    int[] dp = new int[n];  
    char[] s = ss.toCharArray();  
  
    //2. 初始化  
    //初始化 dp[0]    
    if(dp[0] != '0') dp[0] = 1;  
    if(n == 1) return 1;  
  
    //初始化 dp[1]    
    if(s[1] != '0' && s[0] != '0') dp[1] += 1;  
    int t = (s[0] - '0') * 10 + (s[1] - '0');  
    if(t >= 10 && t <= 26) dp[1] += 1;  
  
    //3. 填表  
    for (int i = 2; i < n; i++) {  
        if(s[i] != '0') dp[i] += dp[i-1];  
  
        int tt = (s[i-1] - '0') * 10 + (s[i] - '0');  
        if(tt >= 10 && tt <=26) dp[i] += dp[i-2];  
    }  
  
    return dp[n-1];  
}

• dp 表只需要 n 位，是因为最后是返回 dp[n-1]，可以到
• s[0]-'0' 和 s[1]-'0' 可以得到对应字符的编码

优化原理

处理边界问题以及初始化问题的技巧

在 dp 表中增加一个虚拟节点，把原来初始化起来很麻烦的 s[1] 挤到第三位，而我们初始化对象只是前两位

注意事项：

1. 虚拟节点里面的值，要保证后面的填表是正确的

当我们计算 dp[2] = dp[1] + dp[0] 的时候，dp[1] 是不会出错的，因为原来的 dp 表中就有，但 dp[0] 是我们虚拟出来的节点，这个节点里面存多少，就很重要

一般虚拟节点都是存 0，但这里不行，得存 1

• s[0] 和 s[1] 结合起来能解码成功的话，按照状态表示，就要加上前面的值（新 dp[0]）
• 如果填 0 的话，这个解码方式就忽略掉了，所以不能填 0

1. 下标的映射关系

• s[1-1] != '0'

代码编写

public int numDecodings2(String ss) {  
    int n = ss.length();  
    int[] dp = new int[n+1];  
    char[] s = ss.toCharArray();  
  
    dp[0] = 1;  
    if(s[1-1] != '0') dp[1] = 1;  
  
    for (int i = 2; i <= n; i++) {  
        if(s[i-1] != '0') dp[i] += dp[i-1];  
  
        int tt = (s[i-2] - '0') * 10 + (s[i-1] - '0');  
        if(tt >= 10 && tt <= 26) dp[i] += dp[i-2];  
    }  
  
    return dp[n];  
}

• 初始化 dp 表的时候需要多一位，n+1