5

我参加了 Coursera 上的算法第二部分课程，其中一项任务是解决 Boggle 游戏： http ://coursera.cs.princeton.edu/algs4/assignments/boggle.html

荣誉代码要求我不公开发布解决方案，所以这里是基本算法的伪代码。

visit:
  word <- board[i][j]
  start <- dictionary.match(word, start)
  if start is not null
      visited[i][j] <- true
      word <- prefix + word
      if word is longer than min required length 
          words <- words + word

      for (x, y) ∊ adj(i, j)
          if not visited(x, y)
            visit (x, y)

  visited[i][j] <- false

字典是使用 Trie 实现的。

上面的代码有效，我通过了作业，但后来我看到了这篇博客文章，声称使用动态编程有一个更快的解决方案：

事实证明，我们可以使用一种漂亮的动态编程技术来快速检查一个单词（在这种情况下是从字典中）是否可以从板上构造出来！

这是动态规划思想的核心点：

要在棋盘的第 [i, j] 个位置找到长度为 k 的单词（结束位置），该单词的第 k-1 个字母必须位于 [i, j]。

基本情况是 k = 1。

长度为 1 的字母将在棋盘的第 [i, j] 单元格中找到（结束位置），该单词中唯一的字母与棋盘第 [i, j] 位置的字母匹配。

一旦我们的动态规划表填充了基本情况，我们就可以在此基础上构建任何长度为 k，k > 1 的单词。

不幸的是，作者的解释工作很糟糕，我无法遵循他的解决方案。不过我想，希望这里有人可以向我解释。

PS：

  1. 不是这个问题的重复，因为那个问题不使用 DP；请检查那些重复的快乐手指。

  2. 我已经付出了足够的努力，没有要求任何人做我的功课。我已经有了自己的解决方案。我感兴趣的是学习一种更好的解决问题的方法，如果存在的话。

谢谢！

4

1 回答 1

2

DP（错误）解决方案的想法很简单，假设我们要检查表中是否存在单词“apple”。

  • 让我们创建一个 table dp[k][n][n]，dp[a][x][y]表示带有 length 的单词的前缀是否a可以在 cell 结束(x, y)。

    [a][p][p]
[x][x][l]
[x][x][e]

对于上表，dp[1][0][0] = true, 作为appleisa 等的前缀长度 1 dp[2][0][1] = true。

  • 那么，如何判断dp[a][x][y]真假呢？检查 的所有相邻单元格(x,y)，如果其中一个相邻单元格有dp[a - 1][][] = true，则dp[a][x][y]也是如此。对于我们的示例，对于 cell (0,2)，dp[3][0][2] = true，作为其邻居之一， cell(0,1)具有dp[2][0][1] = true
  • 默认情况下，所有dp[0][x][y] = true
  • 对于任何单元格(x, y)，如果dp[length of word][x][y] = true-> 单词存在于表中。

请注意，当一个字符被使用超过一次时，此解决方案无法检查大小写。

就像如果我们需要查找单词apa并使用上表

dp[1][0][0] = true -> dp[2][0][1] = true -> dp[3][0][0] = true
于 2018-07-12T10:31:21.200 回答