Как найти все слова на доске Boggle с помощью динамического программирования?

Я записался на курс «Алгоритмы, часть II» на 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.

Приведенный выше код работает, и я передал задание, но затем наткнулся на это сообщение в блоге, в котором утверждается, что более быстрое решение с использованием динамического программирования:

Оказывается, мы можем использовать изящную технику динамического программирования, чтобы быстро проверить, можно ли построить слово (в данном случае из словаря) с доски!

Вот основная идея идеи динамического программирования:

Чтобы слово длины k (конечное положение) было найдено в [i, j] -м месте доски, k-1-я буква этого слова должна быть расположена в одной из соседних ячеек [i, j].

Базовый случай k = 1.

Буква длины 1 будет найдена (конечное положение) в [i, j] -й ячейке доски, если единственная буква в слове соответствует букве в [i, j] -м месте доски.

Как только наша таблица динамического программирования заполнена базовым случаем, мы можем построить поверх него для любого слова длины k, k> 1.

К сожалению, автор плохо объяснил, и я не могу понять его решение. Я бы хотел, и надеюсь, что кто-нибудь здесь сможет мне это объяснить.

P.S .:

1. Не дубликат этого вопроса, так как он не использует DP; пожалуйста, держите эти счастливые пальцы под контролем.

2. С моей стороны было продемонстрировано достаточно усилий, и я никого не просил делать уроки. У меня уже есть собственное решение. Что меня интересует, так это узнать лучший способ решения проблемы, если таковой существует.

Спасибо!