Page 230 - Bkhargava_-_Grokaem_algoritmy

самая длинная общая подстрока 229

Если у вас голова идет кругом, не огорчайтесь. Это сложный материал -
собственно, именно поэтому я объясняю его в конце книги! Ниже будет
приведено упражнение, чтобы вы могли самостоятельно потренироваться
в динамическом программировании.

Заполнение таблицы

Сейчас вы уже достаточно хорошо представляете, как должна выглядеть
таблица. По какой формуле заполняются ячейки таблицы? Мы можем не­
много упростить свою задачу, потому что уже знаем решение - у hish и fish
имеется общая подстрока длины 3: ish.
Однако этот факт ничего не говорит о том, какая формула должна ис­
пользоваться. Программисты иногда шутят об использовании алгоритма
Фейнмана. Алгоритм Фейнмана, названный по имени известного физика
Ричарда Фейнмана, работает так:
1. Записать формулировку задачи.

2. Хорошенько подумать.

· 3. Записать решение.

\~

Да, программисты - большие шутники!

По правде говоря, простого способа вычислить формулу для данного случая
не существует. Вам придется экспериментировать и искать работоспособное

www.trk.kg