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

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

Подробнее: Оно выгодно, когда у задачи есть оптимальная подструктура и одни и те же подзадачи встречаются несколько раз. Вместо перебора экспоненциального числа случаев заполняют таблицу от малых подзадач к большим (снизу вверх) или запоминают промежуточные результаты в рекурсивном решении (мемоизация, сверху вниз).

Подробности

Пример: размен монет

Какое минимальное число…

См. также: мемоизация, рекурсия, алгоритмы, О-нотация