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

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

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