我参加了 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.
不幸的是,作者解释得不好,我无法理解他的解决方案。不过我很想,希望这里有人能给我解释一下。
附言:
不是 this 的副本问题,因为那个不使用 DP;请控制住那些喜欢复制的手指。
我已经付出了足够的努力,没有要求任何人做我的功课。我已经有了自己的解决方案。我感兴趣的是学习解决问题的更好方法(如果存在的话)。
谢谢!
最佳答案
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
关于java - 如何使用动态编程找到 Boggle board 上的所有单词?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51297628/