java - 如何使用动态编程找到 Boggle board 上的所有单词？

Question

我参加了 Algorithms, Part II Coursera 上的类(class)，其中一项作业是解决 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 实现的。

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

It turns out, we can use a nifty dynamic programming technique to quickly check whether a word (from the dictionary in this case) can be constructed from the board or not!

Here is core point of the dynamic programming idea:

For a word of length k to be found (end location) at the [i, j]-th location of the board, the k-1'th letter of that word must be located in one of the adjacent cells of [i, j].

The base case is k = 1.

A letter of length 1 will be found (end location) in the [i, j]-th cell of the board of the only letter in the word matches the letter in the [i, j]-th location of the board.

Once our dynamic programming table is populated with the base case, we can build on top of that for any word of length k, k > 1.

不幸的是，作者解释得不好，我无法理解他的解决方案。不过我很想，希望这里有人能给我解释一下。

附言:

1. 不是 this 的副本问题，因为那个不使用 DP；请控制住那些喜欢复制的手指。

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

谢谢!

Answer 1

DP(错误)解决方案的思路很简单，假设我们要检查表中是否存在单词“apple”。

• 让我们创建一个表dp[k][n][n]，其中dp[a][x][y]表示是否长度为 a 的单词前缀可以在单元格 (x, y) 处结束。

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

对于上表，dp[1][0][0] = true，因为apple的前缀长度1是a和 dp[2][0][1] = true 等

• 那么，如何检查 dp[a][x][y] 是否为真？检查 (x,y) 的所有相邻单元格，如果它的邻居之一有 dp[a - 1][][] = true，那么 dp[a][x][y] 也是如此。对于我们的示例，对于单元格 (0,2) ，dp[3][0][2] = true，作为其邻居之一，单元格 ( 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