Динамическое программирование: как не изобретать велосипед дважды. Решение сложных задач по кирпичикам
Фундаментальный метод, который превращает невозможные вычисления в выполнимые. Как числа Фибоначчи и задача о рюкзаке учат нас не решать одно и то же тысячу раз, а складывать ответ из готовых блоков. Мы с вами прошли через множество алгоритмических стратегий: «разделяй и властвуй», жадный подход, поиск в графах. Каждая хороша в своей нише. Но представьте себе задачу, где и делить нечего, и жадность подводит, а полный перебор всех вариантов займет время до конца Вселенной. Именно с такими монстрами...