LeetCode第90题：解码方法

题干

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

'A' -> 1
'B' -> 2
...
'Z' -> 26
复制代码

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，”11106″ 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
复制代码

注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
复制代码

解法：动态规划

首先题目的大意就是让我们对应的数字转码，统计可以最多的转码数。其中还需要我们去考虑一些边界问题，比如当数字为0的情况或者是数组拼接结果是大于26的情况。

首先我们的dp数组的含义是：在i处可以取得的解码方式共有dp[i]种。

我们先来尝试模拟一组，看看能不能推出它的递推公式：

1226
6->dp[i]=1
26->dp[i]=2
226->dp[i]=3
1226->dp[i]=5
复制代码

当我们从后向前遍历时，我们的递推公式实际上就是：

dp[i]=dp[i+1]+dp[i+2]
复制代码

当然这时我们还需要要考虑以下当当前元素为0时的情况

1206
6->dp[i]=1
06->dp[i]=0
206->dp[i]=1
1206->dp[i]=1
复制代码

所以当前元素为0时，dp[i]就等于0。

还有一种情况是当超出范围时：

1186
6->dp[i]=1
86->dp[i]=1
186->dp[i]=2
1286->dp[i]=3
复制代码

因此我们可以写出我们的代码：

注意我们的dp数组初始化时应该比元素组多一个元素，多出的最后一个元素初始化为1，用于后面的迭代加操作。

执行用时：72 ms, 在所有 JavaScript 提交中击败了99.47%的用户

内存消耗：39.4 MB, 在所有 JavaScript 提交中击败了59.15%的用户

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
    // dp数组表示s从0开始的所有的符合条件的
    let len = s.length;
    let dp = new Array(len + 1).fill(0)
    dp[len] = 1;
    dp[len - 1] = 1;
    // 判断第最后一个元素是否为0，若为0则将dp数组的最后一个设置为0
    if (s[len - 1] == 0) {
        dp[len - 1] = 0
    }
    // 开始向前遍历dp数组
    for (let i = len - 2; i >= 0; i--) {
        // 如果元素为0，当前dp值为0
        if (s[i] == '0') {
            dp[i] = 0
            continue
        }
        // 如果当前元素为不符合范围的数值时
        let currentindex = s[i] - '0';
        let nextindex = s[i + 1] - '0';
        let theNumber = currentindex * 10 + nextindex
        // 存储动规方程的第二位
        let temp = 0;
        if (theNumber <= 26) {
            temp = dp[i + 2]
        }
        dp[i] = dp[i + 1] + temp
    }
    return dp[0]
};
复制代码