Грокаем а Иллюстрированное пособие для программистов и любопытствующих

СЛОВА, ПОХОЖИЕ НА “HISH":
. FISH . VISTA
(Это несерьезный пример, поэтому список ограничен всего двумя словами. Вероятно, на практике такой список будет состоять из тысяч слов.)
Итак, Алекс ввел строку hish. Какое слово он хотел ввести на самом деле: fish или vista?
Построение таблицы
Как должна выглядеть таблица для этой задачи? Вы должны ответить на следующие вопросы.

• 
  Какие значения должны содержаться в ячейках?
  
• 
  Как разбить эту задачу на подзадачи?
  
• 
  Каков смысл осей таблицы?
  

В динамическом программировании вы пытаетесь максимизировать неко­торую характеристику. В данном случае ищется самая длинная подстрока, общая в двух словах. Какую общую подстроку содержат hish и fish? А как насчет hish и vista? Именно это требуется вычислить.
Как говорилось ранее, значения в ячейках обычно представляют ту характе­ристику, которую вы пытаетесь оптимизировать. Вероятно, в данном случае этой характеристикой будет число: длина самой длинной подстроки, общей для двух строк.
Как разделить эту задачу на подзадачи? Например, можно заняться срав­нением подстрок. Вместо того чтобы сравнивать hish и fish, можно сначала сравнить his и fis. Каждая ячейка будет содержать длину самой длинной подстроки, общей для двух подстрок. Такое решение также подсказывает, что строками и столбцами таблицы, вероятно, будут два слова. А значит, таблица будет выглядеть примерно так:
и



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

1. 
   Записать формулировку задачи.
   
2. 
   Хорошенько подумать.
   
3. 
   Записать решение.
   

Да, программисты — большие шутники!
По правде говоря, простого способа вычислить формулу для данного случая не существует. Вам придется экспериментировать и искать работоспособное
решение. Иногда алгоритм предоставляет не точный рецепт, а основу, на которую вы наращиваете свою идею.
Попробуйте предложить решение этой задачи самостоятельно. Даю под­сказку — часть таблицы выглядит так:



Чему равны другие значения? Вспомните, что каждая ячейка содержит значение подзадачи. Почему ячейка (3, 3) содержит значение 2? Почему ячейка (3, 4) содержит значение О?
Попытайтесь вывести формулу самостоятельно, прежде чем продолжить читать. Даже если вам не удастся получить правильный ответ, мои объяс­нения покажутся вам намного более понятными.
Решение
Итоговая версия таблицы выглядит так:

	Н	1	S	н
f	о	о	о	о
1	О	1	О	О
	о	о	2	о
н	О	о	О	3

А это моя формула для заполнения ячеек:

Н