LeetCode题解：91. 解码方法，动态规划（优化），JavaScript，详细注释

[chencl1986]

原题链接：91. 解码方法

解题思路：

创建dp数组的注意点：

1. 根据题意，s[0]可能为'0'或'1'，我们可以简单推导出s[0]的初始状态为：dp[1] = s[0] === '0' ? 0 : 1;。
2. 而任意一个位置dp[i]的状态，最多可能和前两个位置有关。
3. 因此创建s.length + 1长度的dp数组，并初始化dp[0] = 1，保证可以向前查找两位的状态，也就是默认虚拟的s[-1]位置是合规的编码。
4. dp[i]对应的字符串位置为s[i - 1]。

该题可以拆解为以下几种场景

1. s[i - 1]的编码范围是1-9，此时不会产生新的编码方法，状态转移方程：dp[i] = dp[i - 1];。
2. s[i - 2] + s[i - 1]的范围是10~26，dp[i]与dp[i - 1]和dp[i - 2]有关，而dp[i - 1]在步骤1已经计算过，因此该条件的状态转移方程：dp[i] += dp[i - 2];。
3. 如果在判断过10和20后，如果s[i - 1]还有出现0，表示当前一定出现了30、40、50等无法解码的情况，可以直接返回0。

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
  // 创建一个s.length + 1长度的数组递推，索引从1到s.length，对应s的每个位置
  // dp[i]对应的字符串位置为s[i - 1]
  let dp = new Array(s.length + 1).fill(0);
  // 由于dp[i]的状态与dp[i - 1]和dp[i - 2]有关，而我们只能创建s[0]的初始状态
  // 0位置设置为1，保证递推能有效进行。
  dp[0] = 1;
  // 创建s[0]的初始状态，为0时解码方法为0
  dp[1] = s[0] === '0' ? 0 : 1;

  // 从s[1]开始递推
  for (let i = 2; i < dp.length; i++) {
    let one = s[i - 1]; // 当前位置的编码
    let two = s[i - 2] + s[i - 1]; // 连续两位的编码

    // 如果当前位置编码为0-9，表示没有新增方法，方法数与dp[i - 1]相同
    if (one >= '1' && one <= '9') {
      dp[i] = dp[i - 1];
    }
    // 如果前两位编码为10-26，表示还需要考虑dp[i - 2]的编码方法，将其累加到dp[i]
    // 而dp[i - 1]已经累加过了，无需重复计算
    if (two >= '10' && two <= '26') {
      dp[i] += dp[i - 2];
    } else if (one === '0') {
      // 当前编码为0，无法解码，返回0
      // 10和20的编码已经处理过，此处不会包含这两个场景
      return 0;
    }
  }

  // 递推到数组最后位置，表示找到了解码方法数量
  return dp[s.length];
};