9.1. Элементарные примеры

Сначала разберём три примера задач на ДП. Именно на этих примерах дальше я и буду показывать различные общие идеи ДП.

9.1.1. Задачи про черепашку

(Не знаю, почему принято формулировать эти задачи именно с упоминанием черепашки, но такая традиция.) Есть клетчатое поле \(N\times M\). В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. а) Сколько у неё разных путей до правого верхнего угла? б) В каждой клетке поля записано некоторое число. Требуется найти максимальную сумму чисел, которую можно набрать по пути в правый верхний угол (для начала не будем обсуждать, как найти путь, на котором сумма будет максимальна, а будем искать только саму эту сумму).

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

Ну и что? А как эти-то задачи решить? Ну, есть одна подзадача, для которой ответ очевиден. До левого нижнего угла а) есть только один способ добраться; б) как ни крути, а сумма, которую при этом наберёшь, равна числу, записанному в этом самом нижнем левом угле. [1] Далее, для клеток левого столбца и нижней строки тоже все очевидно.

Контрольный вопрос 9.1:

Как найти ответы на эти подзадачи?

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

а) \(ans[i,j]=ans[i-1,j]+ans[i,j-1]\);

б) \(ans[i,j]=max(ans[i-1,j],ans[i,j-1])+a[i,j]\),

где в варианте «б» переменная \(a\) обозначает массив, в котором храним числа, изначально записанные в клетках поля.

Примечание

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

Хорошо. Теперь программа пишется просто. Строки и столбцы нумеруем с единицы. Считаем, что координаты правого верхнего угла — \((N,M)\).

а):

ans[1,1]:=1;
for i:=2 to n do
    {сюда надо вставить код инициализации ans[i,1]}
for i:=2 to m do
    {сюда надо вставить код инициализации ans[1,i]}
for i:=2 to n do
    for j:=2 to m do
        ans[i,j]:=ans[i-1,j]+ans[i,j-1];

б):

ans[1,1]:=a[1,1];
for i:=2 to n do
    {сюда надо вставить код инициализации ans[i,1]}
for i:=2 to m do
    {сюда надо вставить код инициализации ans[1,i]}
for i:=2 to n do
    for j:=2 to m do
        ans[i,j]:=max(ans[i-1,j],ans[i,j-1])+a[i,j];

Все. Ответ — в \(ans[N,M]\).

Обратите внимание, какой простой и красивый код. Это — одна из особенностей ДП: код обычно получается весьма простым, пусть даже по началу задача кажется нетривиальной. Красоту этого кода немного портит отдельные два цикла инициализации \(ans[i,1]\) и \(ans[1,i]\), и, соответственно, то, что все циклы идут от 2, а не от 1 — немного позже мы обсудим, как это сделать покрасивее.

9.1.2. Последовательности из нулей и единиц без двух единиц подряд

Эту задачу мы уже обсуждали в теме про перебор. Дано число \(N\). Рассмотрим все \(2^N\) последовательностей из нулей и единиц. Назовём последовательность хорошей, если в ней нигде не встречается две единицы подряд. Требуется посчитать общее количество хороших последовательностей.

Итак, опять. Первая основная идея ДП: будем решать также и более мелкие задачи. А именно, посчитаем не только количество хороших последовательностей длины \(N\), но и хороших последовательностей длины \(i\) для всех \(i\) от 1 до \(N\).

Как это сделать? Опять-таки, попробуем свести каждую подзадачу в общем случае к предыдущим. Вторая основная идея ДП: рассмотрим наиболее общий случай и посмотрим, на что может заканчиваться хорошая последовательность длины \(i\)? Ну, ясно, либо на ноль, либо на единицу. Но ведь мы хотим свести нашу задачу к более мелким? Поэтому давайте подумаем. Если она заканчивается на ноль, то что идёт перед этим нулём? Очевидно, может идти любая хорошая последовательность длины \(i-1\). А если на единицу? Небольшие размышления показывают, что перед единицей может идти только ноль, а перед ним — любая хорошая последовательность длины \(i-2\).

Тут может возникнуть вопрос: я спрашиваю, что идёт перед этой единицей или нулём. А вдруг там ничего нет? В данном случае это будет только при \(i\leq 2\). Но в этом и смысл того, что я предложил рассмотреть наиболее общий случай. Раз наши рассуждения работают плохо при \(i\leq 2\), то рассмотрим потом случай \(i\leq2\) отдельно, как в предыдущей задаче мы отдельно рассмотрели первый столбец и первую строку. Это мне кажется более правильным: сначала рассмотреть общий случай, а потом понять, какие у него есть особые случаи, и рассмотрели эти случаи отдельно. (На самом деле здесь очень хочется рассмотреть случай \(i=0\), считая пустую последовательность, т.е. последовательность из 0 символов, вполне себе хорошей, и тогда случай \(i=2\) не надо будет рассматривать отдельно, но про это я скажу потом ниже.)

Примечание

Лирическое отступление: Вот я тут говорю про особые случаи. На самом деле обычно особые случаи — это весьма неприятные вещи, и стоит стараться написать программу, в которой особых случае будет поменьше. (Конечно, бывают ситуации, когда надо особо учесть случай, который вроде и так правильно обрабатывается программой — например, если это позволит резко ускорить программу, — но я пока такие ситуации не имею ввиду). Среди недостатков особых случаев следует отметить элементарно то, что они очень усложняют программу. Поэтому старайтесь придумывать алгоритмы, которые имеют поменьше особых случаев; ниже мы обсудим особый метод — «введение нулевых элементов», — который позволяет упростить особые случаи в ДП. Но, если особый случай у вас возник, постарайтесь тщательно продумать, откуда и почему он взялся. Например, если при тестировании вы выяснили, что ваша программа вроде работает (я говорю тут очень условно и вовсе не обязательно про программу для задачи про 01-последовательности без двух единиц подряд), но не работает в случае \(M=2\), не спешите писать \(if\), чтобы особо учесть именно этот случай. Сначала подумайте, откуда ноги растут у этого случая. Поймите, почему ваш алгоритм не работает. Во-первых, вы поймёте, нет ли ещё аналогичных случаев, когда ваш алгоритм может не работать по той же причине (например, может оказаться, что ваш алгоритм не работает при \(M\), являющихся степенями двойки, просто вы никакие больше степени двойки не тестировали). Как минимум, это уже позволит вам написать правильный \(if\), который учтёт все такие случаи, а не только тот, который вы заметили. Во-вторых, вы поймёте, нельзя ли немного переделать алгоритм, чтобы он работал всегда. Может оказаться, что не надо никакой if вводить, просто, например, надо сделать какой-нибудь цикл с нуля, а не с единицы. Конец лирического отступления.

Ну что же, теперь все ясно. Ответ для \(i\) равен сумме ответов для \(i-1\) и \(i-2\). Обратите внимание, что тут опять, как и в прошлой задаче а), надо очень внимательно проверить, всё ли мы посчитали и не посчитали ли мы что-нибудь дважды. Проверьте сами. Особые случаи \(i=1\) и \(i=2\) обрабатываем отдельно: вручную посчитали, что \(ans[1]=2\), \(ans[2]=3\).

ans[1]:=2;
ans[2]:=3;
for i:=3 to n do
    ans[i]:=ans[i-1]+ans[i-2];

Всё.

Ещё одно замечание: конечно же, уже при не очень больших \(n\) ответ вылезет за longint и любой другой целочисленный тип, поэтому в общем случае, если надо посчитать точный ответ, тут придётся использовать длинную арифметику; поэтому в последнее время стало модно в подобных случаях просить не точный ответ, а последние его \(k\) цифр или остаток от деления ответа на некоторый модуль \(m\) и т.п., что не требует длинной арифметики, зато требует все действия производить по модулю. Это же справедливо почти для любых других задач, в которых надо посчитать количество объектов (в т.ч. и для предыдущей задачи «а»). Я здесь и далее, чтобы не загромождать текст, не буду писать соответствующий код (т.е. длинную арифметику или операции по модулю), но вы помните об этом. Я надеюсь, что, когда это вам понадобится, вы без проблем сможете его доделать.

9.1.3. Задача о наборе данной суммы данным набором монет

Она же — одна из вариаций задачи о рюкзаке. Есть \(N\) монет. Требуется определить, можно ли с их помощью набрать сумму \(S\), используя каждую монету не более одного раза. (Можно считать, что у нас есть неограниченное количество монет каждого достоинства, получится весьма похожая задача, которая решается практически аналогично, но мы такую задачу пока рассматривать не будем.) (Обратите внимание, что, как и в задаче 1б, я пока не прошу восстановить ответ, т.е. показать, как набирается такая сумма, а только спрашиваю, можно ли.)

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

Итак, пусть у нас есть монеты достоинством \(a_1\), \(a_2\), …, \(a_N\). Для каждого \(i\) от \(1\) до \(N\) и для каждого \(j\) от \(0\) (!) до \(S\) определим, можно ли набрать сумму \(j\) с помощью первых \(i\) монет (т.е. \(a_1\), …, \(a_i\)). (В отличии от предыдущих задач, здесь у нас ответ на каждую подзадачу — типа boolean.) Обратите внимание на, может быть, не очень очевидное, но на самом деле вполне понятное и естественное решение рассмотреть \(j\) от нуля, а не от единицы. \(i\) тоже хочется рассмотреть от нуля, но я пока про это говорить не буду, скажу потом.

Как решить эту подзадачу в самом общем случае? Второй основной принцип ДП: а на что может кончаться наше решение подзадачи, т.е. в данном случае — способ набора суммы \(j\) с помощью первых \(i\) монет. Если немного подумать и вспомнить, какие у нас подзадачи (если это с ходу не очевидно, то можете подумать, как бы вы писали перебор в этой задаче), то становится ясно, что, пожалуй, самое простое следующее. Монета \(a_i\) может входить в наш способ набора суммы \(j\), а может и не входить. Если не входит, то нам надо набрать сумму \(a_i\) с помощью первых \(i-1\) монеты. А если входит, то с помощью первых \(i-1\) монеты надо набрать сумму \(j-a_i\) (Конечно, этот вариант невозможен, если \(j<a_i\). Обратите также внимание, что, если \(j=a_i\), то все хорошо и мы свели нашу задачу к задаче с \(j'=j-a_i=0\). Именно для этого мы и допускали изменение \(j\) от нуля.) Ясно, что таким образом мы перебрали все возможные способы набрать нужную нам сумму, и ответ на нашу задачу положителен, только если положителен ответ на любую из двух (одной, если \(j<a_i\)) полученных подзадач, поэтому

\[\begin{split}ans[i,j]=\left\{ \begin{array}{ll} ans[i-1,j] \mbox{ or } ans[i-1,j-a_i],&\quad j\geq a_i,\\ ans[i-1,j],&\quad j<a_i. \end{array}\right.\end{split}\]

Это в самом общем случае. Ясно, что почти никогда не может каждая подзадача быть самым общим случаем, т.к. нельзя сводить данную подзадачу к предыдущим, а их к ещё более предыдущим и т.д. до бесконечности — это сведение должно когда-то закончиться, а значит, это когда-то и будет особым случаем, т.к. уже не сводится никуда (это аналогично базе матиндукции, я ведь уже говорил об аналогии между математической индукцией и ДП). Но, как я уже говорил, лучше сначала решить общий случай, а потом понимать, что под него не подходит. Пожалуй, в большинстве случаев особым случаем будет просто то, что выводит нас за пределы матрицы ответа (может, можно придумать и более подлые случаи — даже текущая задача уже отчасти даёт пример такого более подлого случая, т.к. приходится разбирать два варианта \(j<a_i\) и \(j\geq a_i\), и в некотором смысле \(j<a_i\) — это особый случай, но мы это уже учли). Здесь видно, что таким особым случаем является \(i=1\), т.к. \(ans[0,j]\) у нас не определено (опять-таки, его легко определить, но я напишу про это отдельно). Так что \(i=1\) придётся обработать особо. Но это довольно просто: с помощью одной монеты \(a_1\) можно набрать только сумму \(a_1\)…нет! ещё и сумму 0 можно. Итак, \(ans[1,0]=ans[1,a_1]=true\), а остальные \(false\). Итак, случай \(i=1\) разобран отдельно, поэтому в основном цикле \(i\) будет идти от 2. (А \(j\) — от нуля; обратите внимание, что \(j=0\) не является особым случаем и вполне нормально обрабатывается по основной формуле.)

fillchar(ans,sizeof(ans),false);
ans[1,0]:=true; ans[1,a[1]]:=true;
for i:=2 to n do
    for j:=0 to s do
        if j<a[i] then
           ans[i,j]:=ans[i-1,j]
        else ans[i,j]:=ans[i-1,j] or ans[i-1,j-a[i]];

Код опять весьма красив, портит только if и двойное присваивание во второй строке. Как красиво избавиться от if’а, я не знаю, а от двойного присваивания — скажу ниже.

Задача 9.2:

Решите задачу, про которую я говорил выше. Есть неограниченное количество монет достоинства \(a_1\), неограниченное количество монет достоинства \(a_2\) и т.д., до \(a_N\). Требуется проверить, можно ли набрать сумму \(S\) этими монетами. Постарайтесь решить её за \(O(NS)\). Решать задачу, конечно, нужно динамикой. Тут вы поймёте, чем так некрасиво двойное присваивание во второй строке.

Задача 9.3:

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

[1]Не знаю, как вам, а мне всегда хочется в этой задаче спросить: а считается в сумме только числа в тех клетках, на которые черепашка переходит, т.е. без начальной — или во всех вообще, считая начальную? Можете подумать, почему для идеи решения задачи это абсолютно все равно и чем будут отличаться алгоритмы решения того и того; а мы дальше будем считать, что учитываются все клетки.