解码方法

题目

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

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

链接：https://leetcode-cn.com/problems/decode-ways

解题思路

本来很简单的一道动态规划，因为边界判断被搞得死去活来
比较重要的两个边界 0和26

1. 出现0那么就需要特殊考虑，思考加入之后会对之前的结果有什么影响。
2. 如果连续出现两个边界，就可以break了，比如出现两个0，[1,0,0]是无法被解码的，另外[1,3,0]因为结尾的两个数中不仅出现了0，且[3,0]的组合也大于26，所以，如果出现这种情况，那么最终结果一定是0；

过滤这些边界后，再来看核心逻辑

1. 首先将前两位的编码手动得出，因为后续的结果需要用dp求出。
2. dp的转移方程为：dp[i] = dp[i-1] + dp[i - 2]; 其实就是斐数列，因为dp[i]的结果一定只可以来自两个结果之和（26以内最多可以是两位数字），前一位拼一个数或者前两位拼两个数。
3. 用dp数组，依据不断相加的子结果得出结果。

代码

class Solution {
    public int numDecodings(String s) {
        if(s==null||s.charAt(0)=='0'||s.length()==0) return 0;
        if (s.length() == 1) return 1;
        int[] dp = new int[s.length()+1];
        dp[0] = 1;
        //手动确定dp[1]的值
        char last1 = s.charAt(0);
        char index1 = s.charAt(1);
        if (last1 == '2' && index1 > '6' || last1 > '2'){
            dp[1] = index1=='0'?0:1;
        }else
        {
            dp[1] = index1=='0'?1:2;
        }
        //循环动态规划
        for (int i = 2; i < s.length(); i++) {
            char last = s.charAt(i-1);
            char cur = s.charAt(i);
            if (last == '2' && cur > '6' || last > '2'){ // 当前位和上一位拼接结果 > 26
                if (cur == '0') {
                    break; //连续两个异常结果，结果肯定为0
                }else
                {
                    dp[i] = dp[i -1];
                }
            }else
            {
                if (cur == '0') {
                    if (last == '0') {
                        break; //连续两个异常结果，结果肯定为0
                    }else
                    {
                        dp[i] = dp[i -2];
                    }
                }else{
                    if (last == '0') {
                        dp[i] = dp[i -1];
                    }else{
                        dp[i] = dp[i -1] + dp[i - 2];
                    }
                }                
            }
        }
        return dp[s.length()-1];
    }
}