Какую задачу можно решить методом динамического программирования

Динамическое программирование. Классические задачи

Здравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа. Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями. Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Последовательности

Классической задачей на последовательности является следующая.

Последовательность Фибоначчи F_n задается формулами: F₁ = 1, F₂ = 1,
F_n = F_{n – 1} + F_{n – 2} при n > 1. Необходимо найти F_n по номеру n.

Один из способов решения, который может показаться логичным и эффективным, — решение с помощью рекурсии:

int F(int n)

Используя такую функцию, мы будем решать задачу «с конца» — будем шаг за шагом уменьшать n, пока не дойдем до известных значений.

Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования:

int F(int n) < if (A[n] != -1) return A[n]; if (n < 2) return 1; else < A[n] = F(n - 1) + F(n - 2); return A[n]; >>

Приведенное решение является корректным и эффективным. Но для данной задачи применимо и более простое решение:

F[0] = 1; F[1] = 1; for (i = 2; i < n; i++) F[i] = F[i - 1] + F[i - 2];

Такое решение можно назвать решением «с начала» — мы первым делом заполняем известные значения, затем находим первое неизвестное значение (F₃), потом следующее и т.д., пока не дойдем до нужного.

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все F_i для i < n), затем, зная решения подзадач, нашли ответ (F_n = F_{n – 1} + F_{n – 2}, F_{n – 1} и F_{n – 2} уже найдены).

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

Чтобы лучше понять суть динамического программирования, сначала более формально определим понятия задачи и подзадачи.

Пусть исходная задача заключается в нахождении некоторого числа T при исходных данных n₁, n₂, . n_k. То есть мы можем говорить о функции T(n₁, n₂, . n_k), значение которой и есть необходимый нам ответ. Тогда подзадачами будем считать задачи
T(i₁, i₂, . i_k) при i₁ < n₁, i₂ < n₂, . i_k < n_k.

Далее мы будем о говорить об одномерном, двумерном и многомерном динамическом программировании при k = 1, k = 2, k > 2, соответственно.

Следующая задача одномерного динамического программирования встречается в различных вариациях.

Задача 1. Посчитать число последовательностей нулей и единиц длины n, в которых не встречаются две идущие подряд единицы.

При n = 1, n = 2 ответ очевиден. Допустим, что мы уже нашли K_{n – 1}, K_{n – 2} — число таких последовательностей длины n – 1 и n – 2.

Посмотрим, какой может быть последовательность длины n. Если последний ее символ равен 0, то первые n – 1 — любая правильная последовательность длины
n – 1 (не важно, заканчивается она нулем или единицей — следом идет 0). Таких последовательностей всего K_{n – 1}. Если последний символ равен 1, то предпоследний символ обязательно должен быть равен 0 (иначе будет две единицы подряд), а первые
n – 2 символа — любая правильная последовательность длины n – 2, число таких последовательностей равно K_{n – 2}.

Таким образом, K₁ = 2, K₂ = 3, K_n = K_{n – 1} + K_{n – 2} при n > 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.

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

Классической задачей двумерного динамического программирования является задача о маршрутах на прямоугольном поле.
В разных формулировках необходимо посчитать число маршрутов или найти маршрут, который является лучшим в некотором смысле.

Приведем пару формулировок таких задач:

Задача 2. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо или вниз. Посчитать, сколькими способами можно попасть из левой верхней клетки в правую нижнюю.

Задача 3. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное число. Необходимо попасть из верхней левой клетки в правую нижнюю. Вес маршрута вычисляется как сумма чисел со всех посещенных клеток. Необходимо найти маршрут с минимальным весом.

Для всех таких задач характерным является то, что каждый отдельный маршрут не может пройти два или более раз по одной и той же клетке.

Рассмотрим более подробно задачу 2. В некоторую клетку с координатами (i,j) можно прийти только сверху или слева, то есть из клеток с координатами (i – 1, j) и (i, j – 1):

Таким образом, для клетки (i, j) число маршрутов A[i][j] будет равно
A[i – 1][j] + A[i][j – 1], то есть задача сводится к двум подзадачам. В данной реализации используется два параметра — i и j — поэтому применительно к данной задаче мы говорим о двумерном динамическом программировании.

Теперь мы можем пройти последовательно по строкам (или по столбцам) массива A, находя число маршрутов для текущей клетки по приведенной выше формуле. Предварительно в A[0][0] необходимо поместить число 1.

В задаче 3 в клетку с координатами (i, j) мы можем попасть из клеток с координатами
(i – 1, j), (i, j – 1) и (i – 1, j – 1). Допустим, что для каждой из этих трех клеток мы уже нашли маршрут минимального веса, а сами веса поместили в W[i – 1][j], W[i][j – 1],
W[i – 1][j – 1]. Чтобы найти минимальный вес для (i, j), необходимо выбрать минимальный из весов W[i – 1][j], W[i][j – 1], W[i – 1][j – 1] и прибавить к нему число, записанное в текущей клетке:

W[i][j] = min(W[i–1][j], W[i][j – 1], W[i – 1][j – 1]) + A[i][j];

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

На следующем рисунке приведен пример исходных данных и одного из шагов алгоритма.

В каждую из уже пройденных клеток ведет ровно одна стрелка. Эта стрелка показывает, с какой стороны необходимо прийти в эту клетку, чтобы получить минимальный вес, записанный в клетке.

После прохождения всего массива необходимо будет проследить сам маршрут из последней клетки, следуя по стрелкам в обратную сторону.

Задачи на подпоследовательности

Рассмотрим задачу о возрастающей подпоследовательности.

Задача 4. Дана последовательность целых чисел. Необходимо найти ее самую длинную строго возрастающую подпоследовательность.

Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности. Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i. Пусть исходная последовательность хранится в массиве A. В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1 i k – 1. Теперь можно найти L[k] следующим образом. Просматриваем все элементы A[i] для 1 i < k – 1. Если
A[i] < A[k], то k-ый элемент может стать продолжением подпоследовательности, окончившейся элементом A[i]. Длина полученной подпоследовательности будет на 1 больше L[i]. Чтобы найти L[k], необходимо перебрать все i от 1 до k – 1:
L[k] = max(L[i]) + 1, где максимум берется по всем i таким, что A[i] < A[k] и
1 i < k.

Здесь максимум из пустого множества будем считать равным 0. В этом случае текущий элемент станет единственным в выбранной последовательности, а не будет продолжением одной из предыдущих. После заполнения массива L длина наибольшей возрастающей подпоследовательности будет равна максимальному элементу L.

Чтобы восстановить саму подпоследовательность, можно для каждого элемента также сохранять номер предыдущего выбранного элемента, например, в массив N.

Рассмотрим решение этой задачи на примере последовательности 2, 8, 5, 9, 12, 6. Поскольку до 2 нет ни одного элемента, то максимальная подпоследовательность содержит только один элемент — L[1] = 1, а перед ним нет ни одного — N[1] = 0. Далее,
2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L[2] = 2, N[2] = 1.

Меньше A[3] = 5 только элемент A[1] = 2, поэтому 5 может стать продолжением только одной подпоследовательности — той, которая содержит 2. Тогда
L[3] = L[1] + 1 = 2, N[3] = 1, так как 2 стоит в позиции с номером 1. Аналогично выполняем еще три шага алгоритма и получаем окончательный результат.

Теперь выбираем максимальный элемент в массиве L и по массиву N восстанавливаем саму подпоследовательность 2, 5, 9, 12.

Еще одной классической задачей динамического программирования является задача о палиндромах.

Задача 5. Дана строка из заглавных букв латинского алфавита. Необходимо найти длину наибольшего палиндрома, который можно получить вычеркиванием некоторых букв из данной строки.

Начнем решать задачу с самых простых подстрок. Для строки из одного символа (то есть подстроки вида S(i, i)) ответ очевиден — ничего вычеркивать не надо, такая строка будет палиндромом. Для строки из двух символов S(i, i + 1) возможны два варианта: если символы равны, то мы имеем палиндром, ничего вычеркивать не надо. Если же символы не равны, то вычеркиваем любой.

Пусть теперь нам дана подстрока S(i, j). Если первый (S[i]) и последний (S[j]) символы подстроки не совпадают, то один из них точно нужно вычеркнуть. Тогда у нас останется подстрока S(i, j – 1) или S(i + 1, j) — то есть мы сведем задачу к подзадаче: L[i][j] = max(L[i][j – 1], L[i + 1][j]). Если же первый и последний символы равны, то мы можем оставить оба, но необходимо знать решение задачи S(i + 1, j – 1):
L[i][j] = L[i + 1][j – 1] + 2.

Рассмотрим решение на примере строки ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подстрокам S(i, i) из одного символа. Затем начинаем рассматривать подстроки длины два. Во всех подстроках, кроме S(4, 5), символы различны, поэтому в соответствующие ячейки запишем 1, а в L[4][5] — 2.

Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подстрок длины 3 получаются следующие значения: в подстроке ABA первая и последняя буквы равны, поэтому
L[1][3] = L[2][2] + 2. В остальных подстроках первая и последняя буквы различны.

BAC: L[2][4] = max(L[2][3], L[3][4]) = 1.
ACC: L[3][5] = max(L[3][4], L[4][5]) = 2.
CCB: L[4][6] = max(L[4][5], L[5][6]) = 2.
CBA: L[5][7] = max(L[5][6], L[6][7]) = 1.

Продолжая далее аналогичные рассуждения, заполним все ячейки под диагональю и в ячейке L[1][7] = 6 получим ответ.

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

динамическое программирование
спортивное программирование
олимпиадные задачи

Метод динамического программирования при принятии микроэкономического решения Текст научной статьи по специальности «Математика»

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ / ДОХОД / ЗАДАЧА / МАТЕМАТИЧЕСКАЯ МОДЕЛЬ / ПРИНЦИП ОПТИМАЛЬНОСТИ Р. БЕЛЛМАНА / РЕКУРРЕНТНАЯ ФОРМУЛА / СОСТОЯНИЕ СИСТЕМЫ / УПРАВЛЕНИЕ / ЦЕЛЕВАЯ ФУНКЦИЯ / DYNAMIC PROGRAMMING / INCOME / PROBLEM / MATHEMATICAL MODEL / A PRINCIPLE OF AN OPTIMALITY OF BELLMAN / RECURRENT FORMULA / CONDITION OF SYSTEM / MANAGEMENT / CRITERION FUNCTION

Аннотация научной статьи по математике, автор научной работы — Сутягина Наталья Игоревна

Динамическое программирование представляет собой метод оптимизации, в котором процесс принятия решения разбит на отдельные этапы. В отличие от линейного программирования динамическое программирование не содержит универсального метода решения задач , поэтому многие задачи имеют свою индивидуальную особенность и требуют специального подхода. Основным методом динамического программирования является метод рекуррентных соотношений, основанный на использовании принципа оптимальности. Основа принципа такова, что каковы бы ни были начальное состояние на любом шаге и управление , выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому система придет в конце данного шага. В статье приводится доказательство принципа оптимальности на основе его геометрического представления, формулируется задача динамического программирования в общем виде и предлагается ее рекуррентное уравнение. Основная суть динамического программирования рассмотрена на примере предприятия, занимающегося разведением и продажей рыбы. Функциональная зависимость дохода предприятия от количества продаваемой рыбы характеризует состояние процесса, то есть параметры состояния. Посредством математических операций выводится рекуррентная формула, позволяющая вычислить оптимальный доход на любом шаге. С учетом практической значимости предлагаемая модель усложняется и в дальнейшем доход предприятия рассматривается в зависимости от разного вида производимой продукции. В итоге полученная математическая модель используется для разработки оптимального плана работы крестьянско-фермерского хозяйства Нижегородской области.

i Надоели баннеры? Вы всегда можете отключить рекламу.

METHOD OF DYNAMIC PROGRAMMING AT ACCEPTANCE OF THE MICROECONOMIC DECISION

Dynamic programming represents a method of optimization in which process of decision-making is broken into separate stages. Unlike linear programming dynamic programming does not contain a universal method of the decision of the problems, therefore many problems have the specific feature and require the special approach. The basic method of dynamic programming is the method of recurrent parities based on use of a principle of optimality. The basis of a principle is those, that what initial condition on any step and the management chosen on this step was, the subsequent managements should get out optimum concerning a condition to which the system will come in the end of the given step. In the article the proof of a principle of an optimality on the basis of it geometric concepts is resulted, the problem of dynamic programming in a general view is stated and its recurrent equation is offered. The basic essence of dynamic programming is considered on an example of the enterprise, engaged by cultivation and sale of a fish. Functional dependence of the income of the enterprise on quantity of a sold fish characterizes a condition of process that is parameters of a condition. By means of mathematical operations the recurrent formula is deduced, allowing calculating the optimum income on any step. In view of the practical importance the offered model becomes complicated and in the further of a profitable enterprise is considered depending on a different type of made production. As a result the received mathematical model is used for development of the optimum plan of work of farms of the Nizhniy Novgorod area.

Текст научной работы на тему «Метод динамического программирования при принятии микроэкономического решения»

The review of concepts of a net cost of production with objective of definition of objects of auditor activity and criteria of an assessment of activity of audited persons is executed. Questions of structure of a net cost of production of animal industries are investigated.

The structure of elements and articles of the expenses connected with manufacture of milk and meat in the organizations of animal industries is certain by Methodical recommendations on accounting of expenses for manufacture and calculating of a net cost of production (works, services) in the agricultural organizations. Elements and articles of expenses recommended to application in the organizations of animal industries according to the above-named recommendations are considered.

Positions MSFO № 41 «Agriculture» with objective of an establishment of interrelation of the Russian and international standards of the account and the financial reporting are considered.

Keywords: the analysis, actives, animal industries, expenses, the organizations, branch, sale, production, manufacture, profitability, resources, a net cost, technology.

МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ ПРИ ПРИНЯТИИ МИКРОЭКОНОМИЧЕСКОГО РЕШЕНИЯ

Н. И. Сутягина, кандидат экономических наук, доцент кафедры «Физико-математические науки» Нижегородский государственный инженерно-экономический институт,

Аннотация. Динамическое программирование представляет собой метод оптимизации, в котором процесс принятия решения разбит на отдельные этапы. В отличие от линейного программирования динамическое программирование не содержит универсального метода решения задач, поэтому многие задачи имеют свою индивидуальную особенность и требуют специального подхода. Основным методом динамического программирования является метод рекуррентных соотношений, основанный на использовании принципа оптимальности. Основа принципа такова, что каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому система придет в конце данного шага. В статье приводится доказательство принципа оптимальности на основе его геометрического представления, формулируется задача динамического программирования в общем виде и предлагается ее рекуррентное уравнение. Основная суть динамического программирования рассмотрена на примере предприятия, занимающегося разведением и продажей рыбы. Функциональная зависимость дохода предприятия от количества продаваемой рыбы характеризует состояние процесса, то есть параметры состояния. Посредством математических операций выводится рекуррентная формула, позволяющая вычислить оптимальный доход на любом шаге. С учетом практической значимости предлагаемая модель усложняется и в дальнейшем доход предприятия рассматривается в зависимости от разного вида производимой продукции. В итоге полученная математическая модель используется для разработки оптимального плана работы крестьянско-фермерского хозяйства Нижегородской области.

Ключевые слова: динамическое программирование, доход, задача, математическая модель, принцип оптимальности Р. Беллмана, рекуррентная формула, состояние системы, управление, целевая функция.

Постановка проблемы в общем виде и ее связь с важными научными и практическими задачами. Метод динамического программирования хорошо известен и имеет большое прикладное значение [1-13]. Принцип оптимальности, разработанный Р. Беллманом, позволил многим исследователям решать задачи экономико-математического моделирования и внедрять их в практическую деятельность.

Широкий класс задач стал доступен для рас-четно-теоретических исследований с использова-

нием эффективных алгоритмов, базирующихся на единой основе [14].

Анализ последних исследований и публикаций, в которых рассматривались аспекты этой проблемы. Использованию метода динамического программирования в задачах экономического содержания уделяется достаточно много внимания в работах отечественных и зарубежных авторов (Е. С. Вентцель [15], М. С. Красс [16], Н. Ш. Кре-мер [17], В. И. Соловьев [18], А. И. Стрикалов [19], С. И. Чернышев [14], Дж. Лайтхилл [20] и др).

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

Формирование целей статьи. На основе метода динамического программирования составить модель оптимальной политики предприятия по производству и реализации продукции на примере предприятия, занимающегося разведением и сбытом рыбы.

Изложение основного материала исследования с полным обоснованием полученных научных результатов. Математические модели при описании экономических процессов должны отражать реальные ситуации. Как правило, переменные этих процессов связаны между собой нелинейными за-

конами. К задачам нелинейного распределения и планирования, решение которых можно рассматривать как многошаговый процесс, применим метод динамического программирования. Главная идея, лежащая в основе динамического программирования, известна как принцип оптимальности, сформулированный Р. Беллманом. Основная его суть заключается в следующем: оптимальная политика обладает тем свойством, что каковы бы ни были начальное состояние и начальное решение, последующие решения должны соответствовать оптимальной политике по отношению к состоянию, вытекающему из первого решения.

Приведем доказательство принципа, несмотря на то, что многие авторы рассматривают его как очевидное утверждение. На рисунке 1 показано его интуитивно-геометрическое представление.

Рисунок 1 - Геометрическое представление принципа оптимальности

Непрерывная кривая соответствует оптимальной политике ведения дела от начального состояния А до конечного М через промежуточные состояния В, С, D, . ,М, появляющиеся в результате последовательных решений. Пусть теперь оптимальная политика перехода от В к М изображена пунктирной линией и предположим, что она отличается от политики, представленной сплошной линией. Отсюда следует, что политика, представленная кривой В, С*,В* . М, оказывается лучше, чем политика, представленная кривой В, С, D. М. Следовательно, и политика, представленная кривой A,B,C*,D. M лучше политики А, В, С, В. М. Но последняя, по определению, является оптимальной, а значит, наше предположение о нарушении принципа оптимальности ведет к противоречию. Поэтому можно сделать вывод, что принцип оптимальности выполняется.

В общем виде задачу динамического программирования можно сформулировать следующим образом.

Пусть имеется последовательность состояний

ип_1,ип. Вектор X (х1, Х2. Хп )

управление, переводящее систему из состояния и в состояние ип. Состояние ик системы в конце к-то шага зависит только от предшествующего состояния ик_х и управления на к-м шаге хк и не зависит от предшествующих состояний и управлений. Таким образом, ик = /к (ик_1, хк), к = 1,2. п . Это уравнения состояний. Показатель эффективности к-го шага процесса управления обозначим через Ок = gk (ик_ 15 х). Целевая функция является аддитивной от показателя эффективности каждого

шага: в = £ gk (Ххк). к=1

Таким образом, задача пошаговой оптимизации формулируется таким образом: определить совокупность допустимых управлений х, X. X, переводящих систему из начального состояния и в конечное состояние ип и максимизирующих (или минимизирующих) целевую функцию.

Принцип оптимальности Р. Беллмана позволяет свести эту многомерную задачу оптимизации к последовательности простых задач. Рассмотрим одношаговый процесс ип_х ^ ип. Для того чтобы

весь процесс из и0 в ми был оптимальным необходимо, чтобы последний шаг был выполнен оптимально. Итак, находим максимальный доход S (ип_ 1) за один шаг:

SMn-1) = max g„ (un-1> Xn).

Теперь рассмотрим двухшаговый процесс Un_2 ^ ии_! ^ u. Доход за два шага будет равен 8п-\(ип-2,x„_i)+ S(u„-1), поскольку второй шаг обязательно должен быть оптимальным! Но U-i = Л-i(u„~2,хи_i). В результате этого для получения максимального дохода S2 (ии_2) за два последних шага надо опять решить простую задачу:

S2 (Un-2 ) = maX Xn-l) + S1 (fn-1 (Un-2 > Xn-1 ))>

Таким образом, мы получаем рекуррентные уравнения Р. Беллмана

В частности, при k = n -1 мы получим:

Рассмотрим суть динамического программирования на примере крестьянско-фермерского хозяйства, занимающегося разведением и продажей рыбы. Основной экономической проблемой всех товаропроизводителей является ответ на вопрос: какую часть доходов следует сохранить, а не тратить?

Пусть фермер решил разводить рыбу на продажу. Он приобрел и0 тонн рыбы и запустил ее в пруд. Через год у него будет еи0(с > 1) тонн рыбы. Часть x тонн рыбы он продаст, а другую часть и тонн оставит на вырост, и т.д. Таким образом, мы получаем уравнения состояний: и = си0 -x, и = c^i -X, . ,и = сиИ_1 -xn. Пусть на каждом k - том шаге фермер имеет доход g(xk). Анализируя рыбный рынок региона, можно сделать вывод, что доход зависит от количества продаваемой рыбы следующим образом: g(xt) = M^/X". Таким образом, на последнем шаге имеем:

Максимальный доход за последние два шага будет определяться из уравнения Р. Беллмана:

82("п-2) = таХ + М>/С(СИИ_2 - Хп_1) ) .

Дифференцируя функцию в фигурных скобках и приравнивая производную к нулю:

получим, что значение хи-1 =

ляет этой функции максимум. Таким

Общие приёмы динамики

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

Рассмотрим такую задачу: требуется найти $n$-ое число Фибоначчи $f_n$, определяемое как

Записав определение выше как функцию, задачу можно решить рекурсивно:

Однако для $n$, превосходящих ~40, такое решение будет работать очень долго. Попытаемся грубо оценить время работы $T(n)$.

Чтобы посчитать $f_n$, нам нужно рекурсивно посчитать $f_$ и $f_$:

$$ T(n) = T(n-2) + T(n-1) + \Theta(1) $$ Для подсчета $f_$ нужно не меньше действий, чем для $f_$. Объединяя с предыдущим, это значит, что $f_n$ нужно хотя бы в два раза больше действий, чем для $f_$: $$ T(n) \ge 2 \cdot T(n-2) $$ А значит, время работы растет экспоненциально: $$ T(n) \ge \Omega(2^) $$

Упражнение. Какое точное суммарное количество рекурсивных вызовов будет при подсчете $f_n$?

Запоминание результатов

Основная идея — сводить задачу к меньшим, и в какой-то момент к базовым — совершенно правильная.

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

Удобнее всего завести массив для всех нужных значений $f_n$ и, вместо рекурсивной функции, инициализировать его базовые значения, а затем пройтись в цикле по всем остальным $f_i$ и посчитать их, используя уже известные после предыдущих итераций $f_$ и $f_$:

(Для больших $n$ в последней строчке будет происходить переполнение, поэтому часто в подобных задачах все значения рассматривают по модулю.)

Динамическим программированием (англ. dynamic programming, ДП, динамика) называется как раз приведенный выше подход, обычно заключающийся в следующих общих шагах:

Свести задачу для $n$ к задаче для чисел, меньших, чем $n$ — то есть найти какую-то рекурсивную формулу.
Создать массив (или какую-нибудь другую структуру данных) для хранения ответов на подзадачи.
Заполнить начало массива вручную (базовые случае, для которых формула не работает).
Обойти массив от известных значений в неизвестные и заполнить ответы по формуле.
Вывести ответ — обычно просто записанный в последней ячейке массиве.

Чтобы решить задачу динамическим программированием, вы должны ответить на 5 вопросов:

Что лежит в массиве? (чаще всего самый важный вопрос)
Как инициализировать начало массива?
Как обходить массив? (чаще всего слева направо, но не всегда)
Какой формулой считать элементы массива?
Где в массиве лежит ответ?

Этим приемом можно решать большое количество важных задач, и в этом разделе мы в этом убедимся.

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

Динамическое программирование - очень широкое понятие, под которое подходит множество алгоритмов, которым посвящены отдельные лекции. Формально, динамическое программирование - способ решения задач с помощью разбиения их на подзадачи и комбинирования ответов на них. Впрочем, для абсолютного большинства людей, не сталкивавшихся раньше с ДП, это определение ничего не объясняет. Попробуем изменить его так, чтобы оно стало немного понятнее, но всё ещё подходило под большинство примеров из олимпиадного программирования:

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

Скорее всего, всё ещё непонятно. Гораздо эффективнее будет привести несколько примеров, начиная с самого элементарного.

Связь между ДП и рекурсией. Последовательность Фибоначчи

Если вы всё же что-то вынесли из приведённого выше определения, то могли заметить, насколько оно похоже на определение рекурсивной функции. На самом деле, ДП - это “всего лишь” способ решения задач на рекурсивные последовательности с сохранением ответа.

Вспомним реализацию расчёта $n$-го числа Фибоначчи из лекции про рекурсию:

Граф вызовов функции fib для n = 6

Идея проста: для вычисления $fib(n)$ нам нужны значения $fib(n - 1)$ и $fib(n - 2)$. Давайте просто считать $fib$ в порядке возрастания $n$, сохраняя результаты в массив.

В большинстве случаев ДП характеризуется тремя главными параметрами:

Начальные значения. Аналогично крайним случаям в рекурсивных функциях.
Формула перехода. Описывает рекурсивную зависимость.
Вычисление ответа. В некоторых случаях ответ может быть не последним значением, а суммой или максимумом по значениям.

Путь в матрице

Задачи на поиск оптимального пути в матрице, наверное, самые классические, после задач на последовательность Фибоначчи. В таких задачах каждой клетке в матрице присвоено некоторое число, и нужно найти путь между двумя клетками с максимальной или минимальной суммой.

Матрица с закрашенным путём между противоположными углами

Приведём решение такой задачи. Будем искать путь между левой верхней и правой нижней клетками с максимальной суммой, если ходить можно только вниз или вправо. Для решения задачи используем следующее ДП: $dp[i][j]$ - максимальная сумма, которую мы можем набрать, дойдя до клетки $(i, j)$. Опишем ДП:

Начальные значения: $dp[0][0] = c[0][0]$ ($c$ - исходная матрица).
Мы находимся в клетке $(0, 0)$, значит мы ещё не двигались, то есть собранная нами сумма равна значению в этой клетке.
Формула перехода: $dp[i][j] = \max(dp[i - 1][j], dp[i][j - 1]) + c[i][j]$
Мы можем перейти в клетку $(i, j)$ либо сверху, либо слева. Выгоднее перейти из той, в которую мы до этого пришли с большей суммой.
Ответ: $dp[n - 1][m - 1]$.

Реализация на C++:

Массив с закрашенными полями, соответвующими НВП

Как можно заметить, сложность такого решения $O(N^2)$. Существует другое решение этой задачи, не такое тривиальное, имеющее имеет сложность $O(N \log N)$. Его можно охарактеризовать как ДП (с натяжкой), но оно значительно отличается от примеров выше. Разберём его.

Будем идти по последовательности слева направо, поддерживая массив $d$, где $d[i]$ - минимальный последний элемент среди всех возможных возрастающих подпоследовательностей длиной $i$. Если таковых не существует, то примем $d[i] = \infty$. Можно достаточно тривиально доказать, что массив $d$ будет строго возрастающим:

По определению $d[i]$ - минимальный последний элемент среди всех подпоследовательностей длиной $i$. Значит, $i$-ый элемент любой подпоследовательности длиной больше $i$ не меньше, чем $d[i]$. Следовательно, не может существовать строго возрастающей подпоследовательности длиной $i + 1$, такой что её последний элемент меньше либо равен $d[i]$, что и требовалось доказать.

Пусть мы обрабатываем очередной элемент $a[i]$, и хотим с его помощью продлить некоторые последовательности. С помощью бинарного поиска найдём в массиве $d$ первый такой индекс $j$, что $a[i] < d[j]$. Утверждается, что элемент $a[j]$. может эффективно продолжить только последовательность длиной $j - 1$. Доказательство: