Page 231 - Bkhargava_-_Grokaem_algoritmy

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

решение. Иногда алгоритм предоставляет не точный рецепт, а основу, на
которую вы наращиваете свою идею.

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

\ s
1 '
f О . о
'

2 о

з
1

Чему равны другие значения? Вспомните, что каждая ячейка содержит
значение подзадачи. Почему ячейка (3, 3) содержит значение 2? Почему
ячейка (3, 4) содержит значение О?

Попытайтесь вывести формулу самостоятельно, прежде чем продолжить
читать. Даже если вам не удастся получить правильный ответ, мои объяс­
нения покажутся вам намного более понятными.

Решение

Итоговая версия таблицы выглядит так:

н s н

F о о о о
1 о 1 о ()
s о о 2 о

н о о о 3

www.trk.kg