Программа для динамического программирования

Обновлено: 03.07.2024

Позднее формулировка понятия была доработана и усовершенствованна до современного вида самим же Беллманом.

Слово «программирование» в контексте «динамическое программирование» на самом деле к классическому пониманию программирования (написанию кода на языке программирования) практически никакого отношения не имеет. Слово «Программирование» имеет такой же смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация».

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

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

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

Задачи комбинаторики, как правило, отвечают на вопрос, сколько существует объектов, обладающих теми или иными свойствами, или сколько существует комбинаторных объектов, обладающих заданными свойствами.

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

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

Неформальное объяснение свойства оптимальности у подзадач может быть продемонстрировано с помощью диаграммы:
Есть задача, которую мы хотим решить при помощи ДП, т.е. найти какой-то план ее решения. Допустим эта задача сложна и сразу решить мы ее не можем. Мы берем малую подзадачу и решаем сначала ее (для x1 ). Затем используя это малое решение x1 , и не меняя структуру этого решения, решаем следующую задачу уже с x1 и x2 . И т.д.

Рис. 1.1. Неформальное объяснение свойства оптимальности у подзадач

Более подробно неформальное объяснение рассматривается ниже.

Примеры, решаемых при помощи динамического программирования задач

Сначала рассмотрим задачи оптимизации (задачи 1-5):

Пример: Есть некоторая карта дорог, представленная в виде графа. Наша цель: добраться из пункта А в пункт Б. Это сделать надо так, чтобы минимизировать расстояние или потраченное топливо.

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

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

Целевая функция: минимизация расходов (либо на издержки на поддержку старого автомобиля, либо на покупку нового).

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

Пример: Игра на бирже, приобретение акций каких-либо компаний

Целевая функция: максимизация средних доходов, т.к. на бирже доход получается вероятностным путем, т.е. это статистический процесс, вероятностный.

Переменная выбора: то, какой портфель вложений будет: сколько акций и какой фирмы нам необходимо купить.

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

Целевая функция: максимизация прибыли.

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

Целевая функция: максимизация вероятности выигрыша или максимизация среднего выигрыша и т.д.

Переменная выбора здесь зависит от конкретной игры.

Комбинаторика:

Пример: Задача на решение того, сколько существует деревьев, у которых определенное число листьев; или сколько существует графов для решения такого-то задания и т.п. Пример: Есть монеты разного достоинства, какими способами можно вернуть сдачу.

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

Понятие динамического программирования

Неформальное объяснение оптимальности подзадач ДП.

Рассмотрим неформальную идею ДП.

Итак, возьмем пример с заводом, изготавливающим мебель.

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

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

Поэтому ДП предлагает следующее:

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

Формальная идея ДП

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

1, 1, 2, 3, 5, 8… , т.е. ряда Фибоначчи

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

function fact (a: integer): integer; begin if (a<=1) then a:=1 else a:=a*(fact(a-1)); fact:=a; end;

Давайте подумаем, почему же так получается? Например, для вычисления fact(30) мы сначала вычисляем fact(29), для вычисления fact(29) нужно fact(28). Но при этом наша программа «забывает», что fact(28) мы уже вычисляли при поиске fibo(29). -->

Кроме того, может возникнуть такой вопрос: для того чтобы найти, например, минимум или максимум, почему бы нам не найти производную? или не использовать множества Ла-Гранжа, или другие методы аппарата математического анализа? Зачем нужно ДП, если есть большой арсенал средств?

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

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

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

Простой пример решения задач при помощи ДП

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

Пример: Необходимо вычислить сумму n чисел: 1 + 2 + 3 + . + n

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

Начнем с суммы одного первого элемента, т.е. просто берем первый элемент:
F(1) = 1
теперь с помощью решения для первого элемента, решим
F(2) = F(1) + 2 = 1 + 2 = 3 , т.е. надо взять сумму первого элемента и добавить к нему второй элемент
F(3) = F(2) + 3 = 6
по аналогии продолжаем и получаем целевую функцию:
F(n) = F(n-1) + An

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

Простой пример, где пока неоправданно используется ДП (искусственно), демонстрирует принцип идей ДП.

Рассмотрим еще один пример.

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

Решение:

Рассмотрим самые простые варианты (подзадачи):

Рассмотрим пример из i ступенек

Как мы можем попасть на i ступеньку:

с i-1 ступеньки, а на i-1 ступеньку мы могли попасть a_i-1 способами
с i-2 ступеньки, а на i-2 ступеньку мы могли попасть a_i-2 способами

Например, как попасть на 4-ю ступеньку:

Т.о., общее количество способов попасть на i ступеньку:
f(a_i) = f(a_i-1) + f(a_i-2)

Определим начальные значения, с которых следует начинать решать задачу.
Если начинать с 1, то формула соответствует нахождению последовательности чисел Фибоначчи.

Мы видим, что задача по сути комбинаторная (т.е. количество способов сделать что-либо) свелась к вычислению некоторой рекуррентной последовательности.

Задание 1: реализовать пример для первых десяти ступенек (по сути, первые 10 чисел ряда Фибоначчи), используя рекурсию.

Дополните код:

var c:integer; procedure getKolSposob(i,n: integer); begin writeln (i+n,' '); inc(c); if . then getKolSposob(. ) end; begin c:=1; getKolSposob(0,1); end.

Изучение

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

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

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

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

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

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

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

Почему динамическое программирование эффективно? Рекурсия против DP

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

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

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

Примеры динамического программирования

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

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

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

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

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

По сути, это то, как динамическое программирование работает и в программах.

Факторная проблема

Мы можем увидеть в реальной жизни, насколько динамическое программирование более эффективно, чем рекурсия, но давайте посмотрим, как это работает с кодом Python!

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

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

Динамическое программирование очень похоже на рекурсию, при этом:

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

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

Классическая задача — числа Фибоначчи

Последовательность Фибоначчи Fn задается формулами: F1 = 1, F2 = 1, Fn = Fn – 1 + Fn – 2 при n > 1. Необходимо найти Fn по номеру n.

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

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

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

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

Приведенное решение корректно и эффективно. Но можно поступить ещё проще:

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

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все F[i] для i < n), затем, зная решения подзадач, нашли ответ.

Задача о кузнечике — количество способов

Рассмотрим следующую задачу. На числовой прямой сидит кузнечик, который может прыгать вправо на одну или на две единицы. Первоначально кузнечик находится в точке с координатой 1. Определите количество различных маршрутов кузнечика, приводящих его в точку с координатой n.

Обозначим количество маршрутов кузнечика, ведущих в точку с координатой n, как K[n]. Прежде всего заметим, что существует ровно один маршрут из точки 1 в точку 1 — он не содержит ни одного прыжка. В точку 2 можно прыгнуть единственным способом — из точки 1.

Как вычислить K[n]? В точку кузнечик может попасть двумя способами — из точки при помощи прыжка длиной 2 и из точки прыжком длины 1. То есть число способов попасть в точку n равно сумме числа способов попасть в точку (n-1) и (n-2), что позволяет выписать рекуррентное соотношение: K[n] = K[n-1] + K[n-2] .

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

Упражнение №1

Решите задачу о количестве способов достичь точки n из точки 1, если кузнечик умеет прыгать +1, +2 и +3.

Упражнение №2

Решите задачу о количестве способов достичь точки n из точки 1, если кузнечик умеет прыгать +1, +2 и *3.

Задача о кузнечике со стоимостями посещения точек

Пусть кузнечик прыгает на одну или две точки вперед, а за прыжок в каждую точку необходимо заплатить определенную стоимость, различную для различных точек. Стоимость прыжка в точку i задается значением price[i] списка price. Необходимо найти минимальную стоимость маршрута кузнечика из точки 0 в точку n.

На этот раз нам необходимо модифицировать определение целевой функции. Пусть C[n] — минимальная стоимость пути из 1 в n.

Выведем рекуррентное соотношение для этой функции.Чтобы попасть в точку n мы должны попасть в неё последним прыжком из (n-1) или (n-2). Минимальные стоимости этих маршрутов будут равны С[n-1] и С[n-2] соответственно, к ним придется добавить значение price[n] за прыжок в клетку n. Но из двух клеток мы можем выбрать любую.

Нужно выбрать тот маршрут, который имеет наименьшую стоимость: C[n] = min(C[n-1], C[n-2]) + price[n]

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

Упражнение №3

Напишите функцию calculate_min_cost(n, price) вычисления наименьшей стоимость достижения клетки n из клетки 1

Восстановление наиболее выгодной траектории

Итак, мы нашли список С, где будет записана минимальная стоимость маршрута для всех точек от 1 до n.

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

Для восстановления ответа будем для каждой точки запоминать номер точки prev[i], из которой кузнечик попал в точку i, если он будет передвигаться по пути минимальной стоимости. То есть prev[i] — это точка, предшествующая точке с номером i на пути минимальной стоимости (также говорят, что Prev — это массив предшественников). Как определить prev[i]? Если C[i-1] < C[i-2] , то кузнечик попал в точку i из точки (i-1), поэтому prev[i] = i - 1, иначе prev[i] = i - 2.

Для восстановления пути необходимо начать с точки n и переходить от каждой точки к ее предшественнику, пока путь не дойдет до начальной точки с номером 0. Номера всех вершин будем добавлять в список path. В конце в список path добавляется начальная вершина номер 1, которая не была обработана в основном цикле, а затем весь список path разворачивается в обратном порядке (т. к. вершины добавляются в обратном порядке, от конечной к начальной).

Упражнение №4

Модифицируйте алгоритм вычисления значений целевой функции так, чтобы вычислить значения prev[i], и восстановите траекторию наименьшей стоимости из точки 1 в точку n.

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

Игра с ферзём

Рассмотрим игру «Ферзя в угол» для двух игроков. В левом верхнем углу доски размером N*M находится ферзь, который может двигаться только вправо-вниз. Игроки по очереди двигают ферзя, то есть за один ход игрок может переместить ферзя либо по вертикали вниз, либо по горизонтали вправо, либо во диагонали вправо-вниз. Выигрывает игрок, который поставит ферзя в правый нижний угол. Необходимо определить, какой из игроков может выиграть в этой игре независимо от ходов другого игрока (имеет выигрышную стратегию).

Будем заполнять доску знаками «+» и «-». Знак «+» будет означать, что данная клетка является выигрышной для ходящего с неё игрока (то есть если ферзь стоит в этой клетке, то игрок, который делает ход, может всегда выиграть), а знак «-» означает, что он проигрывает. Клетки последней строки, последнего столбца и диагонали, ведущей из правого нижнего угла необходимо отметить, как «+», так как если ферзь стоит в этой клетке, то ходящий игрок может выиграть одним ходом.

Но в правом нижнем углу необходимо поставить знак «-» — если ферзь стоит в углу, то тот игрок, которых должен делать ход, уже проиграл.

Теперь рассмотрим две клетки, из которых можно пойти только в те клетки, в которых записан знак «+». В этих клетках нужно записать знак «-» — если ферзь стоит в этих клетках, то какой бы ход не сделал ходящий игрок, ферзь окажется в клетке, в которой стоит знак «+», то есть выигрывает ходящий игрок. Значит, тот, кто сейчас ходит — всегда проигрывает.

Но теперь в те клетки, из которых можно попасть в клетку, в которой стоит знак «-» за один ход, необходимо записать знак «+» — если ферзь стоит в этой клетке, то игрок, который делает ход, может выиграть, если передвинет ферзя в клетку, в которой стоит знак «-»:

Дальше таблица заполняется аналогично. В клетке ставиться знак «+», если есть ход, который ведет в клетку, в которой стоит знак «--». В клетке ставится знак «-», если все ходы из этой клетки ведут в клетки, в которых записан знак «+».

Продолжая таким образом, можно определить выигрывающего игрока для любой начальной клетки.

Упражнение №5

Реализовать алгоритм поиска выигрышных и проигрышных позиций в игре с ферзём на прямоугольном поле M на N, где N — высота, а M — ширина поля.

Упражнение №6

Реализовать алгоритм поиска выигрышных и проигрышных позиций в аналогичной игре, но ходы делает король (только вправо, вниз и по диагонали).

Числа Фибоначчи определяются так: $F_0 = 0, F_1 = 1, F_n = F_ + F_$ .

Эту задачу можно решить рекурсивно:

Однако это будет работать очень долго. 20-е число посчитать еще можно будет, а 40-е число - нет. И не потому, что числа большие. А потому, что мы будем делать слишком много лишней работы. Число операций будет экспоненциально относительно $N$ .

Почему? Потому что, чтобы посчитать N-е число, нам нужно будет независимо посчитать (N-1)-е число и (N-2)-е число, и это в минимум в два раза больше действий, чем нужно для (N-2). А значит, для подсчета N-го числа Фибоначчи необходимо 2 раза посчитать (N-2)-е число, и это занимает в два раза больше времени, а значит это хотя бы $2^\frac$ действий.

Это ну слишком долго, и главное, что это легко исправляется. Давайте просто не считать лишних действий - если мы один раз посчитали $F_k$ , то давайте запомним, чему оно равно, и в следующий раз, когда оно нам понадобится, мы используем его сразу. Удобнее всего сохранить числа Фибоначчи прямо в массиве:

И этот способ легко работает для больших $N$ , так как работает за $O(N)$ - всего один проход по массиву (правда здесь ответ мы будем считать по модулю $10^9$ , потому что иначе числа получатся слишком слишком большими):

Это и называется динамическим программированием (или динамикой, ДП). Основная идея состоит в том, чтобы * свести задачу для $N$ к задаче для чисел, меньших, чем $N$ (с помощью формулы) * хранить все ответы в массиве * заполнить начало массива вручную (для которых формула не работает) * обойти массив и заполнить ответы по формуле * вывести ответ откуда-то из этого массива

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

Одномерная динамика: кузнечик

Рассмотрим такую задачу:

Есть полоска $1\times N$ , кузнечик стоит на первой клетке, он может прыгать вперед на 1, 2, 3 клетки. Сколько есть способов добраться от начальной клетки до последней?

Как решать такие задачи? Нужно придумать рекуррентную формулу, как ответ для N зависит от ответа для меньших чисел.

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

Пусть dp[x] - это количество способов добраться от 1 клетки до клетки номер x.

dp[1] = 1 способ (стоять на месте)
dp[2] = 1 способ ( $1 \rightarrow 2$ )
dp[3] = 2 способа ( $1 \rightarrow 2 \rightarrow 3$ и $1 \rightarrow 3$ )
dp[4] = 4 способа ( $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ и $1 \rightarrow 3 \rightarrow 4$ и $1 \rightarrow 2 \rightarrow 4$ и $1 \rightarrow 4$ )
dp[5] = 7 способов ( $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 2 \rightarrow 3 \rightarrow 5$ и $1 \rightarrow 3 \rightarrow 5$ и $1 \rightarrow 2 \rightarrow 5$ )

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

Какой последний прыжок кузнечика в его пути до N-й клетки? Один из трех вариантов: * $(N - 1) \rightarrow N$ * $(N - 2) \rightarrow N$ * $(N - 3) \rightarrow N$

То есть все пути до $N$ разбиваются на 3 группы. Причем мы знаем сколько путей в каждой группе. В первой из них ровно dp[N - 1] путей - столько путей идут до (N-1)-й клетки, и дальше идет еще один прыжок. Во второй и третьей группах поэтому тоже dp[N - 2] и dp[N-3] путей.

Так что формула получается такой: dp[N] = dp[N - 3] + dp[N - 2] + dp[N - 1].

Очень похоже на числа Фибоначчи, да? Можете посмотреть на числа, которые мы уже выписали, там все отлично подходит:

dp[4] = 4 = 1 + 1 + 2 = dp[1] + dp[2] + dp[3]

dp[5] = 7 = 1 + 2 + 4 = dp[2] + dp[3] + dp[4].

Так что программа пишется легко:

Давайте изменим немного задачу: Теперь некоторые из клеток закрыты. То есть нам известно про конкретные клетки, что на них кузнечик прыгать не может. Тогда задача все еще решается так же, только нужно убедиться, что dp[x] = 0 для всех запрещенных x!

Также немного перепишем код, чтобы не писать отдельно случаи для 2 и 3, а также чтобы не писать в формуле сумму трех чисел (а представьте, что в задаче не 3, а 100). Будем инициализировать только dp[1]. А ко всем следующим значениям dp[i] будет прибавлять dp[i - k], где k = 1, 2, 3. Причем, если i - k < 1, то мы будем игнорировать такие клетки, и этим самым мы избавились от необходимости прописывать ответ для dp[2] и dp[3].

Двумерная динамика: черепашка

Теперь рассмотрим такую задачу:

На каждой клетке двумерной таблички написано, сколько там лежит монет. Черепашка стоит в клетке 1x1 (верхней левой), и может двигаться только на одну клетку вниз, или на одну клетку вправо. Нужно найти максимальное число монет, которое может набрать черепашка по пути к нижней правой клетке NxM.

Первое, что приходит в голову - это просто идти черепашкой в ту клетку из соседних, где лежит больше монет. К сожалению, эта жадная стратегия не всегда работает. Например, на такой доске жадная черепашка пошла бы по следу из единичек, хотя гораздо выгоднее пойти сначала по нулям, а потом найти там большие горстки монет (40, 70, 100):

Тут нас снова спасает динамика. Давайте сводить задачу к предыдущей! Задачей назовем “сколько максимально монет можно набрать на пути от $0\times0$ до $i\times j$ ” (заменим 1-нумерацию на 0-нумерацию). Будем хранить это в двумерном массиве dp в клетке dp[i][j].

Сразу понятны некоторые свойства этого массива: * Он размера NxM * dp[0][0] = COINS[0][0] * ответ на всю задачу лежит в dp[N - 1][M - 1]

Но гораздо важнее придумать формулу для подсчета dp[i][j] через предыдущие. Легко посчитать первую строку и первый столбец: * dp[0][k] = dp[0][k - 1] + COINS[0][k] * dp[k][0] = dp[k - 1][0] + COINS[k][0]

Так как до этих клеток есть ровно один путь.

Но что делать, если есть много путей до клетки dp[i][j]? Снова разобьем их на на несколько групп в зависимости от последнего хода (! важный трюк, запомните). Последний ход был: * либо из [i][j - 1] * либо из [i - 1][j]

Поэтому формула для максимального числа монет такая: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j].

Ну все, достаточно пройтись правильно по двумерному массиву (построчно сверху вних, а в каждой строке слева направо) и заполнить этот массив.

В отличие от жадного алгоритма, динамическое программирование находит оптимальное решение - это, в данном случае, 113 монет.

Восстановление ответа

В последней задаче было здорово найти, что в оптимальном пути черепашки набирается 113 монет, но интересно, что именно это за путь. Такую задачу называют восстановлением ответа в динамике.

Есть два способа, которыми можно это сделать.

Хранить в массив prev откуда ты пришел в эту клетку.

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

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

Вместо хранения массива prev догадаться по массиву dp, откуда именно черепашка пришла в эту клетку.

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

Задание

Решите как можно больше задач из простого контеста:

А также решите как можно больше задач из сложного контеста:

Разбор еще нескольких задач

Давайте разберем еще несколько задач.

Последовательности без 3 единиц подряд

Условие:

Определите количество последовательностей из нулей и единиц длины $N$ , в которых никакие три единицы не стоят рядом.

Решение:

Давайте хранить в $dp[N]$ ровно число таких последовательностей длины $N$ (это первое, что должно приходить в голову).

Давайте посмотрим для начала для маленьких чисел:

$dp[0] = 1 (\text)$
$dp[1] = 2 (0, 1)$
$dp[2] = 4 (00, 01, 10, 11)$
$dp[3] = 7 (000, 001, 010, 011, 100, 101, 110)$
$dp[4] = 13 (0000, 0001, 0010, 0011, 0100, 0101, 0110, 1000, 1001, 1010, 1011, 1100, 1101)$

Сходу закономерность можно не увидеть. Нужно догадаться сгруппировать эти числа по том, сколько в конце единичек. Например, для dp[4]:

0 единичек в конце: $0000, 0010, 0100, 0110, 1000, 1010, 1100$ - их ровно семь, как для $N=3$ , потому что первые 3 числа могут быть любые (но без трех единиц подряд), а четвертое - 0
1 единичка в конце: $0001, 0101, 1001, 1101$ - их ровно четыре, как для $N=2$ , потому что первые 2 числа могут быть любые (но без 3 единиц подряд), а два последних - 01
2 единички в конце: $0011, 1011$ - их ровно две, как для $N=1$ , потому что первое число может быть любым (но без 3 единиц подряд), а три последних - 011

Так мы замечаем и доказываем формулу: $dp[N] = dp[N-1] + dp[N-2] + dp[N-3]$

Теперь за $O(N)$ ее легко посчитать.

Лесенки

Условие:

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

Решение:

Если считать, что $dp[N]$ - это число лесенок из $N$ кубиков, то никакой закономерности скорее всего найти не получится.

По числам построить закономерность сложно, и по самим лесенкам тоже. Не видно какого-то рассуждения вида “ко всем лесенкам размера N-1 можно положить на любой слой еще один кубик”, иногда ведь и нельзя.

Тут нам помогает введение дополнительного параметра. Нас просят решить одномерную задачу (для $N$ ), а мы решим двумерную задачу для $n$ и $m$ . Давайте зафиксируем размер самого нижнего слоя и назовем его размер $m$ .

То есть $dp[n][m] = $“число лесенок, состоящих из $N$ кубиков, таких, что самый нижний слой состоит из $M$ кубиков”.

Как это связано с нашей задачей? Ответ на нашу задачу равен $dp[N][1] + dp[N][2] + \ldots + dp[N][N]$ .

Какая есть формула для такой постановки задачи? Размер нижнего слоя у нас зафиксирован и равен $m$ , осталость $n-m$ кубиков на верхних слоях. Логично перебрать размер второго снизу слоя, который может быть любым от $1$ до $m-1$ : $dp[n][m] = dp[n-m][1] + dp[n-m][2] + \ldots + dp[n-m][m-1]$

Это все пир условии, что $n \geq m$ . Иначе $dp[n][m] = 0$ .

Теперь осталось понять как инициализировать этот массив и аккуратно по нему пройтись. Давайте инициализируем его ровно для случая $n=0, m=0$ :

Пройдемся по массиву сначала для всех m при n = 1, потому для всех m при всех n = 2 и так далее - то есть по строчкам обычными двумя циклами $for$ .

Для $m > 0$ в ячейках $dp[0][m]$ наш алгоритм будет работать и возвращать 0, так как $n < m$ .

Для всех $n > 0$ наша формула будет находить ответ через числа с меньшим n, а значит алгоритм корректен.

Он заполняет табличку размера $N^2$ , обрабатывая каждую клетку за $O(N)$ операций, итоговое время работы - $O(N^3)$ .

Читайте также: