leetcode91. 解码方法(动态规划)

一条包含字母 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) 。

答题：
看到题目第一反应，肯定是最优规划嘛，第k位的可能性只和其前两位相关。做的时候，发现有些小复杂，怪不得通过率不高，不过还是解出来了。
这道题其实只要想好了，连续两位出现的数字时，可以怎么解码就行。
‘00’–没办法解码(1)
‘01’–必须分开(2)
‘10’–必须一起(3)
‘30’–不能解码(4)
‘26’–分开合并都可以(5)
‘35’–必须分开(6)

代码：

public int numDecodings(String s) {
    int len = s.length();
    int[] ans = new int[len + 1];
    //设置默认1
    ans[0] = 1;
    char[] chars = s.toCharArray();
    //字母转数字，方便计算
    int[] nums = new int[len];
    for (int i = 0; i < len; i++) {
        nums[i] = chars[i] - '0';
    }
    //第一位如果是'0',那就没后续了
    if (nums[0] == 0) {
        return 0;
    }
    //那就是一种
    ans[1] = 1;
    for (int i = 2; i <= len; i++) {
        int value = nums[i - 2] * 10 + nums[i - 1];
        if (value == 0) {
            //(1)这就是连续两个0,答案很简单，就是0
            return 0;
        } else if (nums[i - 2] == 0) {
            //(2)前一个是0,不存在'0X'的字母，所以只可能最后一位单独字母
            ans[i] = ans[i - 1];
        } else if (nums[i - 1] == 0) {
            //后一位是0，那就看前一位是不是1或者2了
            if (nums[i - 2] <= 2) {
                //(3)'0'是没办法变成字母的，但是'10','20'可以
                ans[i] = ans[i - 2];
            } else {
                //(4)连续出现'30'或者'40'这种的，是没办法解的
                return 0;
            }
        } else if (value <= 26) {
            //(5)走到现在，如果最后两位是可以解码成，那就是两种可能性都可以
            ans[i] = ans[i - 1] + ans[i - 2];
        } else {
            //(6)那就是最后两位数字太大
            ans[i] = ans[i - 1];
        }
    }
    return ans[len];
}