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

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

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

Основные подходы

1. Мемоизация (Top-down) — рекурсия с сохранением промежуточных результатов.
2. Табуляция (Bottom-up) — последовательное заполнение таблицы снизу вверх.