时间戳

首页 > 解决方案 > 需要帮助了解此动态编程解决方案

algorithm - 需要帮助了解此动态编程解决方案

问题描述

所以被问到的问题是：

使用以下映射将包含来自 AZ 的字母的消息编码为数字：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个仅包含数字的非空字符串，确定解码它的方法总数。

示例 1：

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

示例 2：

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

我解决它的效率非常低，正在寻找其他解决方案，发现动态编程是解决这个问题的好方法。由于 DP 对我来说是新的，我一直在阅读它，现在回到我看到的解决方案，我试图理解这个人使用的自下而下方法背后的逻辑。

function numDecodings(s) {
  if (s.length === 0) return 0;

  const N = s.length;
  const dp = Array(N+1).fill(0);

  dp[0] = 1;
  dp[1] = s[0] === '0' ? 0 : 1;

  for (let i = 2; i <= N; i++) {
    if (s[i-1] !== '0') {
      dp[i] += dp[i-1];
    }
    if (s[i-2] === '1' || s[i-2] === '2' && s[i-1] <= '6') {
      dp[i] += dp[i-2];
    }
  }

  return dp[N];
}

标签： algorithmdynamic-programming

解决方案

首先，让我们理顺一些术语：

  • 有“自上而下”和“自下而上”的方法。“自下而下”不是一个有用的术语。
  • DP 是一种“自下而上”的方法，因为每个解决方案都基于较小和较晚的解决方案。

该代码有一个“备忘录”数组，dp. 您可能会在阅读中看到“记忆”一词。这意味着，当我们第一次计算特定子问题的解决方案时，我们将对其进行记录（记住解决方案），并由参数索引。此后，任何时候我们需要解决方案，我们都会简单地查找它而不是重新计算它。

在字符串中的每个位置，我们记住到目前为止有多少种方法可以对字符串进行编码，然后计算当我们将当前字符添加到该前缀时总共有多少种方法。

非常简短：

  • 如果当前字符不是 0，那么我们可以计算一种方法来继续任何先前的字符串：将其视为对字母 ai 的编码。在这种情况下，到目前为止的每个编码都仍然有效，所以我们将这个计数向前推进：dp[i] += dp[i-1]。
  • 如果前一个字符和当前字符形成一个合法的编码，那么我们也可以将它们作为一个 2 位编码（字母 jz），并将这个 2 字符代码之前的计数结转：dp[i] += dp[i-1].

这就是算法的全部内容。请注意，这并不能处理所有可能的数字序列：如果代码到达没有可能继续的点，它将简单地允许dp[i]保持 0，并继续而不发出消息。例如，给定输入12000226，该算法将识别三种编码方式12，将其扩展为包含atfor 120，然后在遇到接下来的两个零时重置。然后它从 next 重新开始2，并会找到 3 种方法来编码字符串的其余部分，并3作为结果返回。

推荐阅读