9.3. Восстановление решения в задачах на ДП

До сих пор мы обсуждали только те ситуации, когда ответ на задачу выражался одним числом (или boolean’ом). Но во многих задачах может быть нужно также вывести, как получить такой ответ. Например, в задаче про черепашку с поиском пути с наибольшей суммой может понадобиться не только вывести эту сумму, но и сам путь. Аналогично в задаче о наборе данной суммы с помощью данного набора монет может понадобиться вывести какой-нибудь способ набора.

В задачах на ДП в подавляющем большинстве случаев восстановление ответа делается легко, если результаты решения каждой подзадачи уже вычислены и сохранены в соответствующей матрице. Для восстановления ответа напишем процедуру \(out\), которая будет выводить ответ для произвольной подзадачи. Она будет принимать в качестве параметров собственно подзадачу (например, координаты клетки в задаче про черепашку, или величины \(i\) и \(j\) в задаче про монеты) и выводить (в выходной файл или какой-нибудь массив) решение этой подзадачи (т.е. оптимальный путь или способ набора этой суммы; естественно, в последнем случае мы будем запускать процедуру, только если решение этой подзадачи существует). Можно то же самое сказать по-другому: есть некоторый элемент массива (матрицы) ответов, который хранит максимальную сумму или информацию о том, можно ли набрать данную сумму, — процедура \(out\) будет выводить подтверждение этого значения: выводить сам путь с этой суммой или сам способ набора.

9.3.1. Примеры вывода решения

Как мы это будем писать процедуру \(out\)? На самом деле, зная рекуррентное соотношение (я буду его называть именно так, хотя, как я уже говорил, на самом деле достаточен алгоритм, не обязательно чёткая формула), все делается элементарно. Действительно, пусть в задаче про черепашку мы хотим вывести оптимальный путь до клетки \((i,j)\). Вспоминая рекуррентное соотношение, мы знаем, что этот оптимальный путь — это либо путь до клетки \((i-1,j)\) и шаг вправо (считаем, что первое число в координатах — это номер столбца), либо путь до клетки \((i,j-1)\) и шаг вверх. Более того, зная матрицу \(ans\), мы можем легко определить, какой из двух вариантов имеет место: если \(ans[i-1,j]>ans[i,j-1]\), то первый, иначе второй (ну, если \(ans[i-1,j]=ans[i,j-1]\), то оба). Ну тогда все просто; последняя важная идея — это то, что оптимальный путь до клетки \((i-1,j)\) или до \((i,j-1)\) можно вывести просто рекурсивным запуском процедуры \(out\).

procedure out(i,j);
begin
...
if ans[i-1,j]>ans[i,j-1] then begin
   out(i-1,j);
   write('R');
end else begin
   out(i,j-1);
   write('U');
end;
end;

Итак, ещё раз. Что делает эта процедура. Она определяет, на что заканчивается оптимальный маршрут для клетки \((i,j)\). Если он заканчивается на шаг вправо, то этот маршрут на самом деле — маршрут до клетки \((i-1,j)\), после чего идёт шаг вправо. Соответственно, процедура и поступает: она выводит маршрут до клетки \((i-1,j)\), после чего выводит символ ’R’. Аналогично второй случай.

Осталось только одно: как при вычислении массива \(ans\) мы особо рассматривали некоторые случаи, так и тут в процедуре \(out\) их тоже надо рассмотреть особо (если это не сделать, то будет много всего плохого, в первую очередь — бесконечная рекурсия). Эти особые случаи были \(i=1\) или \(j=1\), поэтому надо добавить соответствующие if’ы в начало процедуры:

procedure out(i,j);
begin
if (i=1)and(j=1) then exit;
if i=1 then begin
   out(i,j-1);
   write('U');
   exit;
end;
if (j=1) then begin
   out(i-1,j);
   write('R');
   exit;
end;
if ans[i-1,j]>ans[i,j-1] then begin
   out(i-1,j);
   write('R');
end else begin
   out(i,j-1);
   write('U');
end;
end;

(Конечно, в случае \(i=1\) и \(j\neq 1\) можно просто вывести строчку из нужного количества символов ’U’, но мне кажется проще и более естественно и тут писать аналогично основному варианту; то же самое и для симметричного случая \(j=1\).) (Этот код приведён для случая, когда мы не ввели нулевые элементы. Если их ввести, то от первые if’ы резко упростятся.)

Задача 9.13:

Напишите процедуру \(out\) для случая, когда мы ввели нулевые элементы массива так, как это было сказано в соответствующем разделе.

А для задачи про монеты? Все просто и совершенно аналогично. Будет процедура \(out(i,j)\), которая будет выводить способ набора суммы \(j\) с помощью первых \(i\) монет. Конечно, если такого способа не существует (т.е. \(ans[i,j]=false\)), то такой вызов бессмысленен — мы будем считать, что процедура \(out\) всегда будет вызываться с параметрами, для которых решение существует. Тогда мы, ещё когда придумывали рекуррентное соотношение, поняли, что это решение либо включает монету \(a_i\), либо не включает. Сейчас, когда мы уже насчитали всю матрицу \(ans\), определить, какой из двух случаев имеет место, легко: если \(j\geq a_i\) И \(ans[i-1,j-a_i]=true\), то решение включает \(i\)-ю монету, иначе нет (на самом деле, конечно, может быть так, что возможны оба варианта, но тогда в данной задаче, ясно, все равно, какой из вариантов выбрать). Итак,

procedure out(i,j)
begin
if i=0 then exit;
if (j>=a[i])and(ans[i-1,j-a[i]]) then begin
   out(i-1,j-a[i]);
   write(i,' ');
end else
    out(i-1,j);
end;

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

Обратите ещё внимание на то, как автоматически получается, что мы никогда не вызываем \(out\) с параметрами, для которых нет решения. Действительно, если массив \(ans\) насчитан правильно и решение для \((i,j)\) существует, то в соответствии с рекуррентной формулой оно существует или для \((i-1,j-a_i)\), или для \((i-1,j)\), причём первый вариант может иметь место только при \(j\geq a_i\). Поэтому, если для \((i,j)\) решение существует, то процедура \(out\) сделает рекурсивный вызов для \((i',j')\) обязательно таких, что для них решение тоже существует. Осталось нам убедиться, что вызов \(out\) из главной программы выполняется только для таких \((i,j)\), для которых есть решение — а это наверняка так, нам же не надо вызывать \(out\), если решения нет. Вообще, главная программа будет иметь вид типа

begin
считать N, S, массив a
насчитать массив ans как было показано раньше
if (ans[N,S]) then begin
   writeln('yes');
   out(N,S);
end else writeln('no');
end.

Естественно, если ответ ’no’, то \(out\) мы не вызываем.

9.3.2. Общая концепция написания процедуры \(out\)

Итак, ещё раз общая концепция восстановления решения. Когда вы, придумывая рекуррентное соотношение, сводите текущую подзадачу к более мелким, вы сразу автоматически понимаете, как должно выглядеть оптимальное решение. Соответственно и процедуру \(out\) вы пишете, опираясь на это понимание и используя рекурсивный вызов для вывода ответа на ту подзадачу или те подзадачи, к которым вы свели текущую подзадачу. Особенно думать при написании процедуры \(out\) не надо, все, что надо было придумать, вы уже придумали, когда выводили рекуррентное соотношение. А теперь только вспомните его. Оно даёт сведение текущей подзадачи к более мелким — и тогда, в точности следуя ему, можно свести вывод решения на текущую подзадачу к выводу решения на более мелкие подзадачи, и применить рекурсию для вывода этих более мелких решений.

Проиллюстрирую еще раз на примере про черепашку: вы знаете, что решение для \((i,j)\) это или решение для \((i-1,j)\) и шаг вправо, либо решение до клетки \((i,j-1)\) и шаг вверх. Это вы должны были понять и осознать еще при выводе рекуррентного соотношения, без этого понимания у вас в принципе не получится решение динамикой. Но если вы это уже поняли, то вы тут же это понимание применяете для процедуры \(out\), ничего дополнительно думать не надо.

Еще раз, это важно:

Важно

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

На самом деле, далеко не всегда последовательность действий в процедуре \(out\) одна и та же: сначала вызвать \(out\) для подзадачи, потом вывести что-то ещё. Может быть так, что нужно вызвать \(out\) для одной подзадачи, потом что-то вывести, потом вызвать \(out\) для другой подзадачи; может быть так, что надо что-то вывести, потом вызвать \(out\) для подзадачи, потом ещё что-то вывести и т.д. — в каждой конкретной задаче вполне очевидно, какой именно вариант имеет место: когда вы продумываете рекуррентное соотношение, вы сразу понимаете, как будет выглядеть соответствующее решение, — и какой бы вариант ни был нужен, его очень легко реализовать в процедуре \(out\).

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

Задача 9.14:

Избавьтесь от рекурсии в какой-нибудь из приведённых выше процедур \(out\)

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

Единственная проблема, которая вас может ожидать при написании процедуры \(out\) таким способом — это необходимость определять, какой именно из нескольких случаев в рекуррентном соотношении имел место (пришли мы слева или снизу; использовали мы или нет \(i\)-ю монету и т.п.). Пока с этим было просто; на самом деле, наверное, всегда можно просто ещё раз повторить вычисления, которые проводились в рекуррентном соотношении, и тем самым все понять. Но нередко писать это лень, да ещё дублирование кода создаст опасность лишних ошибок, наконец, повторять все проверки легко, пока у нас всего два варианта (как и было везде выше), но их может быть больше — и заново перебирать их будет лишней тратой времени. В таком случае может быть полезно при вычислении массива \(ans\) сразу запоминать, какой из случаев в рекуррентном соотношении имел место («откуда мы пришли в эту клетку»), в специальном массиве \(from\), и потом просто использовать его значения (если вы помните алгоритмы поиска кратчайших путей в графе, то это все очень аналогично). Пример будет ниже.

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

9.3.3. Вывод лексикографически первого решения

Иногда бывает, что при наличии нескольких решений требуют вывести какое-нибудь определённое, например, в некотором смысле лексикографически наименьшее.

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

Но бывают случаи, когда можно обойтись лишь простым изменением процедуры \(out\) или небольшой коррекцией основного цикла вычисления массива \(ans\). Например (пример какой-то неестественный получается, но ничего другого в голову с ходу не приходит), пусть нам нужно по возможность использовать монеты с большими номерами. А именно, если можно вывести решение с монетой \(a_N\), то вывести его, иначе (никуда не денешься) — без монеты \(a_N\); среди всех таких решений по возможности выбрать решение с \(a_{N-1}\), среди всех их — с \(a_{N-2}\) и т.д. Такой в некотором смысле аналог лексикографического порядка.

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

Пример: пусть у нас массив \(a\) (достоинства монет) равен \([1, 2, 4, 3]\), и нам надо набрать сумму 5. У нас есть два варианта: взять первую и третью монеты, или вторую и четвертую. В смысле сказанного в предыдущем абзаце это получаются решения \(3, 1\) или \(4, 2\). Так вот, нам надо вывести второе решение, потому что оно лексикографически больше, чем первое.

Это требование элементарно удовлетворяется; на самом деле, если подумать, то приведённая выше процедура \(out\) именно это и делает: ведь, выводя решение \(out(i,j)\), надо, если можно, вывести решение, содержащее \(i\)-ю монету, и только если такого нет, то вывести решение без неё. Именно это мы и делаем. Если бы мы написали по-другому:

procedure out(i,j)
begin
if i=0 then exit;
if (ans[i-1,j]) then
    out(i-1,j);
else begin
   out(i-1,j-a[i]);
   write(i,' ');
end;
end;

т.е. по возможности не использовали бы \(i\)-ую монету, то выводили бы другое решение.

Т.е. то же самое, но по-другому: иногда в процедуре \(out\) у нас возможны сразу несколько вариантов, и мы должны сделать выбор (я об этом уже говорил перед предыдущем примером процедуры \(out\) для задачи про монеты). Если этот выбор сделать грамотно, то можно вывести то решение, которое надо.

Если же вы выводите решение с использованием массива \(from\), то в процедуре \(out\) у вас выбора нет, вы тупо следуете массиву \(from\). Но тогда есть выбор при вычислении массива \(from\); обычно он легко осуществляется просто правильным порядка перебора вариантов; пример будет ниже.

Ещё обратите внимание, что в наиболее простых вариантах мы выводим решение с конца, поэтому и выбирать мы можем только так: сначала выбирать последний элемент, только выбрав его, выбирать предпоследний и т.д. Если это именно то, что надо (например, как в рассмотренном только что варианте с монетами), то круто, иначе (например, если бы потребовали по возможности использовать первую монету и т.д.), были бы проблемы. Их зачастую можно решить, решая задачу «задом наперёд»; в данном случае достаточно просто обратить порядок монет, сделав последнюю первой и наоборот. Даже более того, очень часто задача в некотором смысле симметрична, и потому, когда надо, можно смотреть, на что начинается решение (и в задаче про монеты смотреть, можно ли набрать сумму \(j\) с помощью монет \(a_i\), \(a_{i+1}\), …, \(a_N\), сводя эту задачу к задаче с большим \(i\)).

Более конкретно: пусть мы записываем решение про монеты более естественным образом, а именно пишем номер (но не значение) первой используемой монеты, потом второй и т.д. И нам надо из многих решений вывести первое в лексикографическом порядке. Тогда надо по возможности брать первую монету, потом вторую и т.д., и соответственно можно просто написать динамику, которая вычисляет \(ans[i,j]\), используя значения \(ans[i+1, j']\), т.е. делая переход не к \(i-1\), а к \(i+1\), ну и соответственно цикл по \(i\) будет по убыванию, и лексикографически первый ответ легко выводится.

Задача 9.15:

Научитесь выводить первое в лексикографическим порядке решение задачи про черепашку с набором максимальной суммы. Решение задаём строкой из букв ’R’ и ’U’ и лексикографический порядок на этих строках определяем как всегда.

9.3.4. Пример с массивом \(from\): задача про наибольшую возрастающую подпоследовательность

Дан массив \(a_1\), \(a_2\), …, \(a_N\). Требуется вычеркнуть из него как можно меньше чисел так, чтобы получилась строго возрастающая последовательность. (Конечно, можно потребовать нестрого возрастающую, или убывающую — все будет аналогично.) Например, для массива 1 3 3 1 4 2 решением будет оставить 1 3 4.

Будем решать задачу динамическим программированием. На самом деле есть интересный способ решить задачу за \(O(N\log N)\), но мы не будем мучиться и решим её за \(O(N^2)\). Итак, для каждого \(i\) посчитаем длину наибольшей возрастающей подпоследовательности куска \(a_1\), …, \(a_i\) при условии (!), что \(a_i\) обязательно входит в эту последовательность, и запишем эту длину в \(ans[i]\). Например, для приведённого выше примера массив \(ans\) должен будет иметь вид 1 2 2 1 3 2. Ясно, что мы считаем?

Выбор подзадач кажется немного странным. Может захотеться реализовать ДП для тех подзадач, которые первыми приходят в голову: \(ans[i]\) будет длиной наибольшей возрастающей последовательности среди первых \(i\) чисел, без требования, чтобы \(ans[i]\) обязательно входил в нее. Но такие подзадачи свести к более мелким довольно сложно, или, скорее всего, вообще невозможно. Дело в том, что последовательность должна быть возрастающей, а потому при сведении к более мелким подзадачам нам важно как-то быть уверенными, что ответ на более мелкую подзадачу не закончится на слишком большое число — поэтому проще всего знать это самое число. Вообще, это довольно стандартный приём — в задачах на выбор элементов потребовать, чтобы последний элемент обязательно входил.

Считать на самом деле это просто. На что может заканчиваться такая подпоследовательность? Ну ясно дело, что на \(a_i\) по условию — поэтому будем смотреть на число, стоящее перед ним. Ясно, что это может быть любое число, идущее до \(a_i\) в начальном массиве и строго меньшее, чем \(a_i\), т.е. это может быть такое \(a_j\), что \(1\leq j<i\) и \(a_j<a_i\). Более того, ясно, что тогда началом нашей подпоследовательности будет наибольшая возрастающая подпоследовательность, заканчивающаяся на \(a_j\) — а её длину мы уже посчитали; она равна \(ans[j]\). Итак, ясно, что \(ans[i]\) равен 1 плюс максимум \(ans[j]\) по всем \(j\) таким, что \(1\leq j<i\) и \(a_j<a_i\). Можно записать и явное рекуррентное выражение, но я думаю, что смысла в этом мало: понимания оно не прибавит, только потребует дополнительных размышлений на тему того, что же тут такое написано — т.е. этот как раз тот случай, про который я говорил выше: достаточно алгоритма вычисления \(ans[i]\), а соотношение, собственно, не важно.

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

Итак, получаем следующий цикл:

ans[0]:=0;
a[0]:=-inf; //ну понятно, число, которое меньше любых a[i]
for i:=1 to n do begin
    max:=-1;
    for j:=0 to i-1 do
        if (a[j]<a[i])and(ans[j]>max) then
           max:=ans[j];
    ans[i]:=max+1;
end;

Ещё раз. Мы вычисляем максимум \(ans[j]\) по всем \(j\) таким, что \(0\leq j<i\) (мы ввели нулевой элемент и потому тут стоит ноль, а не единица; обратите внимание, что это условие учитывается границами цикла) и \(a_j<a_i\) (а это уже приходится писать в if), и тогда \(ans[i]\) на единицу больше этого максимума.

Тут немного нетривиально находится ответ на задачу: раньше у нас всегда ответ лежал в \(ans[N]\) и т.п., а здесь ответ, очевидно, есть максимальное из всех значений \(ans\). Но это несложно и вы это сможете сделать сами; обсудим то, ради чего я тут и даю этот пример.

Как вывести саму подпоследовательность-решение? Ясно, мы напишем процедуру \(out(i)\), которая будет выводить наибольшую возрастающую подпоследовательность, заканчивающуюся на \(a_i\). Но как вспомнить то \(j\), на котором мы нашли максимум? На самом деле можно в процедуре \(out\) ещё раз пробежаться по всем \(j\) и найти подходящий, но проще будет завести массив \(from\), в \(i\)-м элементе которого мы и будем хранить то \(j\), на котором пришёлся максимум:

ans[0]:=0;
a[0]:=-inf; //ну понятно, число, которое меньше любых a[i]
for i:=1 to n do begin
    max:=-1;
    for j:=0 to i-1 do
        if (a[j]<a[i])and(ans[j]>max) then begin
           max:=ans[j];
           maxj:=j;
        end;
    ans[i]:=max+1;
    from[i]:=maxj;
end;

Обратите (здесь и далее) внимание, что элемент \(from[0]\) нам не нужен.

Теперь \(out\) пишется совсем элементарно:

procedure out(i)
begin
if i=0 then exit;
out(from[i]);
write(a[i],' ');
end;

(мы выводим сами числа, а не их номера). Обратите внимание на простоту кода: никаких вариантов, просто тупо следуем массиву \(from\).

А если теперь хотим лексикографически наименьшую последовательность в ответе? Ну например так: надо вывести ответ с наименьшим последним элементом, среди всех таких — ответ с наименьшим предпоследним элементом и т.д. (на самом деле, по-моему, в силу специфики данной конкретной задачи, здесь это то же самое, что и требовать наименьший первый элемент, среди всех таких наименьший второй элемент и т.д., т.е. настоящий лексикографический минимум, можете над этим подумать — но для простоты мы рассмотрим именно такой «задом-на-перед» лексикографический порядок). Раньше мы бы в \(out\) это учли, а теперь придётся учитывать в вычислении \(from\) — но ясно, что это просто требует при прочих равных отдавать предпочтение меньшим по значению элементам \(a_j\):

...
    for j:=0 to i-1 do
        if (a[j]<a[i]) then
           if (ans[j]>max)or((ans[j]=max)and(a[j]<a[maxj])) then begin
              max:=ans[j];
              maxj:=j;
           end;
...

Т.е. если мы нашли ещё один вариант с такой же длиной, то иногда имеет смысл перезаписать наше старое решение.

Все, после этого будет выводиться нужное решение.

9.3.5. Пример на нетривиальную процедуру \(out\): алгоритм Флойда с сохранением промежуточной вершины

Я не буду подробно рассказывать здесь алгоритм Флойда, просто скажу, что он ищет кратчайшие пути между всеми парами вершин графа, при этом в одном из вариантов в массиве \(from\) в элементе \(from[i,j]\) хранит некоторую вершину, лежащую на кратчайшем пути из \(i\) в \(j\), причем это вовсе не обязательно первая или последняя вершина на пути. (И, если кратчайший путь из \(i\) в \(j\) не проходит ни через какие другие вершины, то храним \(-1\)). Тогда процедуру \(out\) придётся писать так:

procedure out(i,j)
begin
if from[i,j]=-1 then begin
   write(i,' ');
   exit;
end;
out(i,from[i,j]);
out(from[i,j],j);
end;

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

(И поэтому избавиться от рекурсии, заменив на цикл for, тут уже не получится.)

Ещё тут есть тонкость, что такая процедура \(out\) не выводит последнюю вершину пути, иначе на стыке вершина \(from[i,j]\) была бы выведена дважды, но это сейчас не принципиальный момент.