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

Динамическое программирование — это когда у нас есть одна большая задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать.

А.С. Кумок

Динамическое программирование (ДП, динамика) — это метод решений задач совершенно разных классов. Пожалуй, это единственный в своём роде раздел олимпиадного программирования: не алгоритм, не структура данных, а именно метод, идея решения задач. К динамической памяти он, конечно, отношения не имеет.

ДП идейно очень напоминает метод математический индукции. Это очень полезно держать в голове при чтении дальнейшего текста, тогда, может быть, все будет проще.

Может показаться, что ДП — это некий чёткий алгоритм построения решения задачи, т.е. что достаточно его освоить — и все соответствующие задачи будут решаться с ходу, без затруднений. Конечно, это не так; в любых задачах всегда приходится хоть немного, но думать головой. Поэтому смотрите на все, что я тут написал, как на то, что поможет вам в этом думании; в каждой конкретной задаче могут возникнуть дополнительные особенности и т.п.

Оглавление: