写在前面

这是一道比较简单的DP问题，定义dp数组和寻找递推方程都很容易，不过多种情况实在是不太容易考虑周全，做题都成了从用例推情况了，思路实在是不太清晰。

题目

核心思路

题目求解给定字符串的解码方法总数，那么很容易就可以想到，dp[i]表示从字符串开头至i下标的解码方法总数，有了定义，可以来看下面的例子，寻找递推方程。

在上图中，绿色表示未发生合并，直接在前一个子串的基础上新增一个字符；红色表示发生合并，合并后的字符需要加在前两个子串的末尾，由此，很容易想到如下的递推公式：

//可发生合并
dp[i] = dp[i - 2] + dp[i - 1];
//不可发生合并
dp[i] = dp[i - 1];

似乎这样就可以解决了，不过在我提交的时候发现少考虑了很多情况：

• 当前位置为'0'，且可以组成10，20...
• 当前位置为'0'，组成00
• 当前位置不为'0'，且前一位为'0'，如01，02...
• 当前位置不为'0'，且前一位与当前一位组成27，38...
  这些情况考虑不到终归是得不到正确的结果的。

代码

很惭愧，上边的情况考虑的只考虑到了最后一种，然后根据用例添加情况判断后得到了这样的代码：

class Solution {
    public int numDecodings(String s) {
        if(s == null) return 0;
        int n = s.length();
        if(n < 2 && s.charAt(0) != '0') return 1;
        else if(s.charAt(0) == '0') return 0;

        int[] dp = new int[n + 1];
        dp[0] = 1;dp[1] = 1;
        for(int i = 2; i <= n; i++){
            if(s.charAt(i - 1) == '0'){
                if(s.charAt(i - 2) > '2' || s.charAt(i - 2) == '0'){
                    return 0;
                }else{
                    dp[i] = dp[i - 2];
                }
            }else{
                if(s.charAt(i - 2) == '0'){
                    dp[i] = dp[i - 2];
                }else{
                    int temp = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
                    if(temp <= 26){
                        dp[i] += dp[i - 2];
                    }
                    dp[i] += dp[i - 1];
                }
            }
        }
        return dp[n];
    }
}

虽然成功通过了，但是逻辑并不是很清晰，后来通过看官方推荐1ms的题解，才发现这些情况其实都是可以合并的，只要一个条件就可以解决，代码如下：

class Solution {
    public int numDecodings(String s) {

        if(s == null || s.length() == 0){
            return 0;
        }
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        for(int i = 2; i <= s.length(); i++){
            if(s.charAt(i - 1) != '0'){
                dp[i] = dp[i - 1];
            }
            int twodigits = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
            if(twodigits >= 10 && twodigits <= 26){
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length()];
    }
}

每每看到别人简单的代码总会羡慕，不过那都是一点点完善合并出来的，希望自己可以在变强的路上越走越远吧。如果有写的不对的地方还请指出，感恩相遇~