如何使用动态编程在Boggle板上找到所有单词？

Question

我参加了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。

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

一旦用基本情况填充了动态编程表，就可以在长度为k，k> 1的任何单词的基础上进行构建。

不幸的是，作者在解释方面做得很差，我无法遵循他的解决方案。我想不过，希望这里有人可以向我解释。

PS：

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

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

谢谢！

Answer 1

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

• 我们来创建一个表格dp[k][n][n]，with的dp[a][x][y]意思是长度为length的单词的前缀是否a可以以cell结尾(x, y)。

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

对于上表， ，作为isdp[1][0][0] = true的前缀长度 1 等。appleadp[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就像我们需要在上表中查找单词and 一样

dp[1][0][0] = true -> dp[2][0][1] = true -> dp[3][0][0] = true