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

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

Метод активно используется в задачах оптимизации, анализе графов, распределении ресурсов, поиске общих подпоследовательностей и других алгоритмических сценариях. 1

Идея метода была сформулирована в середине XX века математиком Ричардом Беллманом, изучавшим техники оптимизации в условиях неопределённости. 1

Некоторые области применения динамического программирования: биоинформатика, экономика, теория игр и компьютерные науки. 2 Например, в биоинформатике метод используется для выравнивания последовательностей ДНК, а в экономике — для оптимизации портфелей инвестиций. 2