c++ - 动态规划中的表如何工作？

Question

我现在一直在研究动态编程，我在一个网站上看到了一段代码。 问题说写一个函数来检查 C 是否是 A 和 B 的交错。如果 C 包含 A 和 B 的所有字符并且保留各个字符串中所有字符的顺序，则称 C 是交错的 A 和 B。我是什么不明白值是如何填充到二维矩阵中的？

需要帮助:) 链接在这里 http://www.geeksforgeeks.org/check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings-set-2/

// an interleaving of A and B, otherwise false.
bool isInterleaved(char* A, char* B, char* C)
{
  // Find lengths of the two strings
  int M = strlen(A), N = strlen(B);

  // Let us create a 2D table to store solutions of
  // subproblems.  C[i][j] will be true if C[0..i+j-1]
  // is an interleaving of A[0..i-1] and B[0..j-1].
  bool IL[M + 1][N + 1];

  memset(IL, 0, sizeof(IL)); // Initialize all values as false.

  // C can be an interleaving of A and B only of sum
  // of lengths of A & B is equal to length of C.
  if ((M + N) != strlen(C))
    return false;

  // Process all characters of A and B
  for (int i = 0; i <= M; ++i)
  {
    for (int j = 0; j <= N; ++j)
    {
      // two empty strings have an empty string
      // as interleaving
      if (i == 0 && j == 0)
        IL[i][j] = true;

      // A is empty
      else if (i == 0 && B[j - 1] == C[j - 1])
        IL[i][j] = IL[i][j - 1];

      // B is empty
      else if (j == 0 && A[i - 1] == C[i - 1])
        IL[i][j] = IL[i - 1][j];

      // Current character of C matches with current character of A,
      // but doesn't match with current character of B
      else if (A[i - 1] == C[i + j - 1] && B[j - 1] != C[i + j - 1])
        IL[i][j] = IL[i - 1][j];

      // Current character of C matches with current character of B,
      // but doesn't match with current character of A
      else if (A[i - 1] != C[i + j - 1] && B[j - 1] == C[i + j - 1])
        IL[i][j] = IL[i][j - 1];

      // Current character of C matches with that of both A and B
      else if (A[i - 1] == C[i + j - 1] && B[j - 1] == C[i + j - 1])
        IL[i][j] = (IL[i - 1][j] || IL[i][j - 1]);
    }
  }

  return IL[M][N];
}

void test(char *A, char *B, char *C)
{
  if (isInterleaved(A, B, C))
    cout << C << " is interleaved of " << A << " and " << B << endl;
  else
    cout << C << " is not interleaved of " << A << " and " << B << endl;
}

// Driver program to test above functions
int main()
{
  test("XXY", "XXZ", "XXZXXXY");
}

Answer 1

Dynamic programming重新使用子问题的结果来解决问题。子问题是问题的较小版本。通常使用表格来存储子问题的结果。

表的索引是特定于应用程序的；在这种情况下，它们在评论中进行了描述:

// Let us create a 2D table to store solutions of
// subproblems.  IL[i][j] will be true if C[0..i+j-1]
// is an interleaving of A[0..i-1] and B[0..j-1].

(我修正了一个错误，C[i][j]在原始源码中应该是IL[i][j])。

子问题确定A 和B 的子字符串是否是C 的子字符串的交错。IL 数组中的索引确定 的子字符串的长度>A 和 B(第三个子串的长度由其他两个子串的长度隐含)。

例如:

• IL[0][0] 为 true，因为“”(空字符串)和“”交错形成“”。
• IL[0][*] 也是 true，因为 ""和 WHATEVER 交错形成 WHATEVER(此处，* 表示“任何”)。
• IL[*][0] 也是 true，原因与上述类似。
• IL[i][j] 是通过将 C 中的当前字符与 A 和 中的当前字符进行比较来计算的B (查看源代码以确定我所说的“当前”是什么意思)
  • 如果两者都不匹配，则您知道 C 不是交错，因为它包含意外字符。因此，IL[i][j] = false。
  • 如果它匹配 A，那么您还需要检查前面的字符是否也正确交错。这就是动态规划部分发挥作用的地方——您不需要实际查看所有这些字符来检查它们，因为您已经在之前的迭代中完成了该操作。检查的结果(这也是您应该返回的最终结果)存储在 IL 表中，更具体地说，在 IL[i-1][j] .因此，IL[i][j] = IL[i-1][j]。
  • 如果它匹配 B，则执行与上面相同的操作，除了查看 IL[i][j-1]。

如果您无法理解动态规划解决方案，我建议您通过网站上的递归解决方案手动工作。最终，你会意识到你在重复很多比较。您可以通过在第一次必须进行比较时存储比较结果，然后在后续场合重新使用该结果来避免这种重复。