Page 229 - Bkhargava_-_Grokaem_algoritmy

228 Глава 9. Динамическое программирование

И так, Алекс ввел строку hish. Какое слово он хотел ввести на самом деле:
fish или vista?

Построение таблицы

Как должна выглядеть таблица для этой задачи? Вы должны ответить на
следующие вопросы.

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

о Каков смысл осей таблицы?

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

Как говорилось ранее, значения в ячейках обычно представляют ту характе­
ристику, которую вы пытаетесь оптимизировать. Вероятно, в данном случае
этой характеристикой будет число: длина самой длинной подстроки, общей
для двух строк.

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

\ s н

1
'
f

1

www.trk.kg