9.5. Способы написания ДП

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

9.5.1. ДП с просмотром назад

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

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

Все просто, и в большинстве случаев вы именно так и будете писать динамику. Но есть ещё два способа написания динамики, у которых есть определённые преимущества. Читайте далее.

9.5.2. ДП с просмотром вперёд

Это — довольно хитрая идея, я её сначала проиллюстрирую на примере задачи про 01-последовательности. Рассмотрим такой код:

fillchar(ans,sizeof(ans),0);
ans[1]:=2;ans[2]:=1;
for i:=1 to n do begin
    ans[i+1]:=ans[i+1]+ans[i];
    ans[i+2]:=ans[i+2]+ans[i];
end;

Утверждается, что этот код корректно решает задачу о 01-последовательностях. С ходу это может показаться неочевидным, но работает это так. Мы перебираем все подзадачи и, оказавшись в очередной вершине графа подзадач, смотрим, какие вершины зависят от неё, т.е. откуда в неё идут ребра. Мы знаем, что ответ на каждую подзадачу — это сумма ответов на все подзадачи, от которых она зависит. Поэтому мы просто для каждой подзадачи, которая зависит от нашей, добавляем к её ответу наш ответ. Поэтому — главная идея всего этого! — когда мы доберёмся од очередной подзадачи, в соответствующей ячейке таблицы уже будет храниться правильный ответ на неё!

Ещё раз: ответ на задачу с \(i=10\) равен сумме ответов на \(i=9\) и \(i=8\). Изначально \(ans[10]=0\). На восьмой итерации цикла, т.е. при \(i=8\), второй строчкой цикла мы выполним присваивание \(ans[10]:=ans[10]+ans[8]\), в результате чего станет \(ans[10]=ans[8]\). На девятой итерации цикла (при \(i=9\)) мы сделаем \(ans[10]:=ans[10]+ans[9]\), в результате чего \(ans[10]\) станет равным \(ans[9]+ans[8]\), что и требовалось! Поэтому на десятой итерации цикла нам уже ничего не надо делать для вычисления \(ans[10]\): он у нас вычислен!

Если ещё не понятно, то, может быть, все станет понятнее, если промоделировать работу этого цикла:

изначальное состояние массива 2 1 0 0 0
после первой итерации 2 3 2 0 0
после второй итерации 2 3 5 3 0
после третьей итерации 2 3 5 8 5
после четвёртой итерации 2 3 5 8 13

Я надеюсь, теперь совсем понятно; по крайней мере видно, что значения получаются правильные.

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

В чем достоинство такого способа? Основное достоинство в том, что вы ходите по рёбрам графа не в направлении стрелок, а в обратном направлении. Иногда так бывает (я знаю одну такую задачу), когда перебрать задачи, зависящие от данной, легко, а вот перебрать задачи, от которых зависит данная, нетривиально — в таком случае ДП с просмотром вперёд написать проще.

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

Пример: задача про Буратино (не знаю, почему она так называется, но так принято).

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

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

Во входном файле записано расписание телевизионных передач с 9:00:00 до 18:00:00 в следующем формате. В первой строке число \(N\) — количество телевизионных передач в этот период (\(1\leq N\leq 32400\)). В каждой из последующих \(N\) строк записано описание одной передачи: сначала время её начала в формате ЧЧ:ММ:СС (ЧЧ — две цифры, задающие часы, ММ — две цифры, задающие минуты начала, СС — две цифры, задающие секунды начала). А затем через один или несколько пробелов число \(T_i\) — время в секундах, которое папа Карло будет тратить на забивание одного гвоздика, если он перед этим увидит по телевизору эту передачу (\(1\leq T_i\leq 32400\)).

Передачи записаны в хронологическом порядке. Первая передача всегда начинается в 09:00:00. Можно считать, что последняя передача заканчивается в 18:00:00.

(Конец условия задачи)

Не обращайте внимание на технические проблемы в этой задаче (хитрый формат ввода, тонкости с тем, что будет, если он не успеет дозабивать последний гвоздик и т.п.). Обратите внимание на то, что всего секунд с 9:00:00 до 18:00:00 не так уж и много: всего 32400, и никто не мешает вам выделить массив такой длины, и работать за O(количества секунд).

Задача 9.21:

Решите эту задачу.

9.5.3. Рекурсия с запоминанием результата

Оно же ленивое ДП. К этой идее можно придти разными способами, попробую изложить все.

Вообще, зачем нам что-то новое? Мы вроде и так умеем писать ДП, даже зачем-то выучили ДП с просмотром вперёд? Но если подумать, то в обоих рассмотренных выше способах написания ДП есть два недостатка. Первый состоит в том, что нам надо заранее определить, в каком порядке мы будем решать подзадачи, чтобы, когда мы дойдём до очередной подзадачи, все задачи, от которых она зависит, уже были бы обработаны. В простых случаях найти такой порядок не представляет сложностей, но возможны случаи, когда все не так очевидно. Как же найти такой порядок в общем случае? А очевидно. Нам надо упорядочить подзадачи так, чтобы все ребра в графе подзадач шли от более поздних подзадач к более ранним — а ведь это топологическая сортировка, которую мы уже прекрасно знаем!

Есть и другой недостаток у простой реализации ДП. Мы выше всегда вычисляли ответы на каждую подзадачу, при том, что, возможно, не все эти ответы мы будем когда-нибудь использовать. В задаче про черепашку и про 01-последовательности такого эффекта нет, но в задаче про монеты несложно видеть, что нам обычно не обязательно решать каждую подзадачу. Например, там совершенно незачем выяснять, можно ли всеми монетами набрать какую-нибудь сумму, отличную от той, что дана во входном файле. Если все монеты невелики, а сумма достаточно большая, то ясно, что нам не надо смотреть, можем ли мы набрать небольшие суммы почти всеми монетами; если все монеты чётны, то заранее ясно, что нечётные суммы набрать не получится — короче, ясно, что не всегда надо решать все подзадачи. Более того, ясно, что можно придумать много критериев, какие подзадачи не надо решать, но все подобные критерии будут не очень тривиальны, существенно зависеть от входного файла и т.д. — в общем, нужен другой подход.

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

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

function find(i,j:integer):boolean;
begin
if i=0 then begin
   find:=j=0; {понимаете такую конструкцию?}
   exit;
end;
if j<a[i] then
   find:=find(i-1,j)
else find:=find(i-1,j-a[i]) or find(i-1,j);
end;

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

Итак, у нас будет массив \(ans[i,j]\), элементы которого будут иметь следующий смысл: если \(ans[i,j]=-1\), то эту подзадачу мы ещё не решали; \(ans[i,j]=0\) — решали и ответ «нельзя» (набрать сумму \(j\), используя первые \(i\) монет), \(ans[i,j]=1\) — решали и ответ «можно». Тогда получаем код

function find(i,j:integer):boolean;
begin
if i=0 then begin
   find:=j=0;
   exit;
end;
if ans[i,j]=-1 then begin
  if j<a[i] then
    ans[i,j]:=find(i-1,j)
  else begin
    if (find(i-1,j-a[i])=1) or (find(i-1,j)=1) then
      ans[i,j]:=1
    else ans[i,j]:=0;
  end;
end;
find:=ans[i,j];
end;

(Такой страшный if просто чтобы проще понимать было.)

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

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

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

Кстати, помните аргументацию к топсорту? «Процедура \(put\) ставит вершину \(i\) в выходной массив. Прежде чем туда её поставить, она пытается поставить туда все вершины, которые должны идти после \(i\)-ой (напомню, что массив мы заполняем с конца); естественно, это делается рекурсивным вызовом. После того, как это выполнено, можно непосредственно поместить \(i\) в выходной массив.»

(Там, правда, мы хотели получить порядок такой, чтобы все ребра шли слева направо, а сейчас нам надо справа налево, поэтому и заполняли массив с конца и поэтому вершины, куда идут ребра из \(i\)-ой, должны были идти после неё, а сейчас нам надо наоборот.) Аргументация у нашего алгоритма абсолютно аналогичная: процедура \(find\) вычисляет ответ для вершины. Прежде чем его вычислить, она пытается вычислить ответ для всех вершин, от которых зависит \(i\)-ая. После того, как это выполнено, можно непосредственно вычислить ответ для \(i\)-ой вершины. Т.е. ещё раз: то, что мы написали и топсорт — это, фактически, одно и то же, и идеология у них одна и та же.

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