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

Что такое динамическое программирование?

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

Ключевые идеи:

• Оптимальная подструктура — оптимальное решение задачи можно получить из оптимальных решений подзадач
• Перекрывающиеся подзадачи — одни и те же подзадачи встречаются многократно
• Мемоизация — запоминание результатов вычислений