Динамическое программирование (ДП) — метод решения задач путем составления последовательности из подзадач таким образом, что:
первый элемент последовательности (возможно несколько элементов) имеет тривиальное решение последний элемент этой последовательности — это исходная задача каждая задача этой последовательности может быть решена с использованием решения подзадач с меньшими номерами Другими словами, для решения задачи T методом ДП составляется некоторая последовательность подзадач T1, T2, ... Tn такая, что решение задачи T1 уже имеет решение, T = Tn, и самое главное, что зная решения задач T1, T2, ... Ti-1 можно вывести решение задачи Ti для любого i = 2..n .
Доказательство работоспособности метода ДП напрямую следует из принципа математической индукции. Действительно, если нам удастся для некоторой задачи построить вышеупомянутую последовательность, удовлетворяющую данным свойствам, то зная T1 мы легко вычислим T2 (при i=2), а из решений задач T1 и T2 будет следовать решение задачи T3 (при i=3) и т.д. увеличивая значение i мы будем находить решение задачи Ti через ранее решенные задачи до тех пор, пока i не достигнет значения n, а решение задачи Tn эквивалентно решению исходной задачи.
Динамическое программирование обычно придерживается двух подходов к решению задач:
Нисходящее ДП: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач. Восходящее ДП: Все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего ДП в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить решение каких подзадач нам потребуется в дальнейшем. Многие переборные задачи часто имеют динамическое, более эффективное решение благодаря тому, что появляется возможность не вычислять многократно одни и те же промежуточные значения. Принцип ДП используется во многих известных алгоритмах и отражает эффективность данного метода над другими решениями.
Пример решения задачи "Числа Фибоначчи"
Ранее мы уже рассматривали решения данной задачи. Очевидно, что данная задача имеет рекурсивное решение благодаря рекуррентной записи для вычисления элемента: F(n) = F(n-1) + F(n-2). Простое рекурсивное решение неэффективно, т.к. приходится многократно вычислять одни и те же значения элементов ряда. Например, из формул F(4)=F(3)+F(2) и F(3)=F(2)+F(1) следует, что для вычисления F(4) значение F(2) приходится вычислять дважды.
Проведем разбор решения поставленной задачи с использованием ДП. Пусть исходная задача T — это вычисление n-го элемента ряда Фибоначчи. В качестве последовательности подзадач Ti выберем последовательность задач F(i), которые сводятся к вычислению i-го члена ряда. Тогда T1 и T2 нам известны (T1 = T2 = 1), а Tn — это как раз поставленная выше задача. Каждая задача Ti легко может решаться через предшествующие ей задачи: Ti = Ti-1 + Ti-2 (для i=3..n). Поэтому последовательно вычисляя значение Ti мы линейным алгоритмом найдем и последний искомый элемент Tn.
При решении данной задачи методом ДП мы сохраняем все ранее найденные решения и не возвращаемся к повторному их решению в случае необходимости. Это сильно ускоряет процесс вычислений. Заметим, что вовсе не обязательно помнить все решения в массиве, достаточно запоминать только два предыдущих.
