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

 Автора - в студию!!!

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

   Лично мной материал немного литературно "причёсан" и переведён из формата PDF в HTML, в дальнейшем планируется также его снабдить прямыми ссылками на один из ресурсов, где можно решить упоминаемую в статье задачу (по образцу, как это сделано ниже для задачки про черепашку), а также дополнить другим матриалом, который будет гармонично дополнять сведения, изложенные в этой статье. 
   Итак, приступим...

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

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

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

Часть I. Элементарные примеры

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

Ричард Фейнман. Характер физических  законов.

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

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

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

   Ну и что? А как эти-то задачи решить? Ну, есть одна подзадача, для которой ответ очевиден. До левого нижнего угла а) есть только один способ добраться; б) как ни крути, а сумма, которую при этом наберёшь, равна числу, записанному в этом самом нижнем левом угле. Далее, для клеток левого столбца и нижней строки тоже все очевидно. Контрольный вопрос 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] = min(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]:=min(ans[i-1,j],ans[i,j-1])+a[i,j];

   (Мы здесь используем функцию min, чтобы не загромождать код. В реальной программе, может быть, вам удобнее будет заменить её на if).

   Все. Ответ - в ans[N, M].

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

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

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

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

   Тут может возникнуть вопрос: а что идёт перед этой единицей или нулём. А вдруг там ничего нет? В данном случае это будет только при i≤2. Но в этом и смысл того, что предложено рассмотреть наиболее общий случай. Раз наши рассуждения работают плохо при i≤2, то рассмотрим потом случай i≤2 отдельно, как в предыдущей задаче мы отдельно рассмотрели первый столбец и первую строку. Это кажется более правильным: сначала рассмотреть общий случай, а потом понять, какие у него есть особые случаи, и рассмотрели эти случаи отдельно. На самом  деле здесь  очень хочется  рассмотреть случай 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[i1]+ans[i2];

   Всё.

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

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

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

   Итак, пусть у нас есть монеты достоинством a₁, a₂, ..., a_N. Для каждого i от 1 до N и для каждого j от 0 (!) до S определим, можно ли набрать сумму j с помощью первых i монет (т.е. a₁,  ..., 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) полученных подзадач, поэтому

   Это в самом общем случае. Ясно, что почти никогда не может каждая подзадача быть самым общим случаем, т.к. нельзя сводить данную подзадачу к предыдущим, а их к ещё более предыдущим и т.д. до бесконечности это сведение должно когда-то закончиться, а значит, это когда-то и будет особым случаем, т.к. уже не сводится никуда (это аналогично базе матиндукции, мы ведь уже говорили об аналогии между математической индукцией и ДП). Но, как уже говорилось, лучше сначала решить общий случай, а потом понимать, что под него не подходит. Пожалуй, в большинстве случаев особым случае будет просто то, что выводит нас за пределы матрицы ответа (может, можно придумать и более подлые случаи - даже текущая задача уже отчасти даёт пример такого более подлого случая, т.к. приходится разбирать два варианта j<a_i и j≥a_i, и в некотором смысле j<a_i - это особый случай, но мы это уже учли). Здесь видно, что таким особым случаем является i=1, т.к. ans[0, j] у нас не определено (опять-таки, его легко определить, но мы напишем про это отдельно). Так что i=1 придётся обработать особо. Но это довольно просто: с помощью одной монеты a₁ можно набрать только сумму a₁ ... нет! ещё и сумму 0 можно. Итак, ans[1, 0]=ans[1, a]=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[i1,j]          else ans[i,j]:=ans[i1,j] or ans[i1,ja[i]];

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

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

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

Часть II. Фундаментальные основы ДП

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

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

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

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

procedure find(i,j); begin    if (i=N)and(j=M) then begin       check;       exit;    end;    curs:=curs+a[i,j];    if i<N then       find(i+1,j);    if j<M then       find(i,j+1);    curs:=cursa[i,j]; end;

function find(i,j):integer; var n1,n2:integer; begin    if i=1 then begin       if j=1 then          find:=a[1,1]       else find:=find(i,j1)+a[i,j];       exit;    end;    if (j=1) then begin   {i can’t be 1 here}       find:=find(i1,j)+a[i,j];       exit;    end;    n1:=find(i1,j);    n2:=find(i,j1);    if n1<n2 then       find:=n2+a[i,j]    else find:=n1+a[i,j]; end;

   Тут два варианта написания перебора: в левой колонке  полностью в соответствии с тем, как писалось в теме про перебор: процедура find перебирает все пути от клетки (i, j) до (N, M); в правой колонке немного другой вариант: тут функция перебирает все варианты пути от клетки (1, 1) до (i, j) и возвращает максимальную возможную сумму (т.е. find(i, j) возвращает то, что раньше мы называли ans[i, j]). Вдумайтесь в этот вариант, он тоже довольно простой, и полностью соответствует нашему рекуррентному соотношению, и поэтому намного ближе к динамическому  решению, поэтому далее будем иметь ввиду именно его. Тут ещё аккуратно надо проверить, учитывается ли начальная клетка в этих решениях; если нет, а надо, или если учитывается, а не надо, то исправить легко. В первом варианте в главной программе надо запустить find(1, 1), во втором  find(N, M).
     Казалось бы, и ДП, и второй вариант перебора построены на одних и тех же идеях  они вычисляют решение данной подзадачи через решения более мелких. Но ДП работает намного быстрее. Дело в том, что перебор будет по много раз делать одну и ту же работу. Давайте посмотрим работу перебора вглубь хотя бы на три шага:

   Что ж, все ясно. Уже даже здесь видно, что find(N−1, M−1) была запущена  два раза, и, конечно, оба раза честно заново вычисляла максимальную сумму, которую можно набрать по пути от (1, 1) к (N−1, M−1), хотя совершенно понятно, что сколько раз ни запускай её, ответ всегда будет один и тот же. find(N−2, M−1), равно как и find(N−1, M−2) запускалась уже по три раза, и несложно догадаться, что чем дальше будет клетка (i, j) от (N, M), тем больше раз будет запускаться процедура find(i, j). Эти многократные запуски совершенно бессмысленны, т.к. ответ всегда получится один и тот же.

   Этим и пользуется динамическое программирование. Вместо того, чтобы каждый раз, когда понадобиться, заново считать ответ для (i, j), ДП считает его ровно один раз, а далее просто берет уже известный ответ из массива (см. визуализатор на рисунке справа. Автор визуализатора - Василюк Руслана, 11 кл., 2011-2012 уч.г.). На самом деле процедуру find можно написать так, чтобы она сначала проверяла, а не запускалась ли она раньше с этими параметрами, и, если, да, то не вычисляла ответ заново, а просто возвращала результат, полученный при прошлом запуске и заботливо сохранённый в специальном массиве - получится то, что называется "рекурсией с запоминанием результата", и про что будем говорить ниже.

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

   Рассмотрим дерево перебора для нашего примера переборного решения.

   Смысл перекрытия подзадач как раз и состоит в том, что, в частности, выделенные поддеревья одинаковы. Поэтому логично их "объединить", получая то, что логично называть графом подзадач:

   (Естественно, объединяются все экземпляры совпадающих поддеревьев, в частности, все деревья с корнем (N−2, M−1) и т.п.)

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

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

   §2. Принцип оптимальности для подзадач. Ещё один принцип, который необходим вообще для возможности записи рекуррентного соотношения - это принцип оптимальности для подзадач. Если вы решаете задачу на оптимизацию (как в задаче про черепашку с максимизацией суммы), и сводите подзадачу к более мелким, то вам обычно нужно, чтобы решение большой подзадачи содержало в себе решения более мелких. Обычно это значит, что любой кусок (или начало, или конец) оптимального решения подзадачи является оптимальным решением некоторой соответствующей более мелкой подзадачи. Например, в задаче про черепашку любое начало оптимального пути до любой клетки (i, j) будет оптимальным путём до некоторой другой клетки (т.е. если оптимальный путь до клетки (i, j) проходит через клетку (i', j'), то соответствующее начало этого пути будет оптимальным путём до клетки  (i', j')).

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

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

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

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

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

   Но может так быть, что не получается выбрать подзадачи подходящим образом. Например, пусть опять черепашке надо попасть из (1, 1) в (N, M), собрав по дороге максимальную сумму, но при этом заранее известны K векторов, которыми черепашка может воспользоваться - т.е. за один ход черепашка может сдвинуться на любой из этих векторов. Если каждый вектор (x, y) удовлетворяет одновременно трём условиям x≥0, y≥0 и (x, y)≠(0, 0), то задача не очень сложно решается динамикой за O(NMK) (Задание 6: Решите эту задачу; Задание 7: Зачем нужны эти три условия?), но, если поставить дополнительное условие, что каждым вектором можно пользоваться не более одного раза, то простой динамикой задача решаться не будет (в принципе, тут подойдёт динамика по подмножествам, про которую будем говорить ниже, но сложность решения уже не будет полиномиальной, а будет расти как что-нибудь типа NMK2^K).

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

   Задание 9: Вспомните задачу про монеты. Там тоже каждой монетой можно было пользоваться не  более  одного  раза,  но  при  этом  задача  благополучно  решалась  динамикой.  Чем  таким  наша  задача отличается от задачи про монеты? Можете ли придумать какуюнибудь задачу, которая казалась бы близкой к нашей задаче про черепашку, но решалась бы динамикой аналогично задаче про монеты?

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

   §3. Дополнительные замечания.

   1. Введение нулевых элементов.

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

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

   Например, рассмотрим задачу про черепашку с подсчётом количества путей. Раньше у нас были особые случаи i=1 или j=1. А сделаем следующую идею: введём в массиве ans нулевую строку и нулевой столбец, причём, естественно, ans[i,0]=ans[0,i]=0, т.к. до тех клеток невозможно добраться (т.е. есть ноль способов добраться :) ). Теперь несложно видеть, что значения ans[i, j] верно вычисляются по стандартной формуле ans[i, j]=ans[i−1,j]+ans[i, j−1] для всех i и j от 1 до N (или M), кроме ans[1,1], который по этой формуле получается ноль, а не один. Можно оставить ans[1,1] особым случаем, но проще сделать, например, ans[1,0]=1, и тогда все будет совсем легко.

   Аналогично для пути с максимальной суммой можно ввести нулевые строку и столбец и заполнить их значениями −∞ (т.е. меньшими, чем любой возможный ответ на задачу), а элемент ans[1,0] положить равным 0 (или ans[0,1], не важно). Получим:

fillchar(ans,sizeof(ans),0); ans[1,0]:=1; for i:=1 to n do      for j:=1 to m do          ans[i,j]:=ans[i1,j]+ans[i,j1];

// заполнить массив ans значениями inf ans[1,0]:=0; for i:=1 to n do    for j:=1 to m do       ans[i,j]:=min(ans[i1,j],ans[i,j1])+a[i,j];

   Обратите внимание, что, если бы мы оставили ans[1,1] особым случаем, то пришлось бы в цикл добавить if (i<>1) or (j<>1), что было бы не очень приятно. Ещё обратите внимание, что для удобства я весь массив инициализирую нулями (или минус бесконечностями), хотя достаточно только нулевые элементы.

   Итак, общая идея введения нулевых элементов: иногда бывает полезно расширить массив ans и про инициализировать новые элементы так, чтобы все значения в основной части массива можно было вычислять по общей формуле. Именно это является основным критерием корректности введения нулевых элементов. В подавляющем большинстве случаев их значения довольно естественны (конечно, ведь черепашка не может добраться до клетки (3,0) никоим образом  поэтому ans[3,0]=0), но не всегда (ans[1,0] тому пример), поэтому проверяйте корректность введения нулевых элементов именно по тому, что остальные  элементы  считаются  нормально.  Поэтому  полезно  сначала  значения  определять  из  этих  естественных соображений, но потом обязательно проверять, что остальные значения считаются нормально. Ещё раз: единственный критерий правильности определения значений нулевых элементов то, что другие элементы считаются правильно, а различные другие качественные соображения  лишь дополнительная подсказка, хотя нередко и полезная.

   Контрольный вопрос 10: Понимаете ли вы, что остальные элементы в этих примерах считаются корректно?

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

   Название "нулевые элементы", конечно, довольно условно - они могут в разных задачах быть и первыми, и минус первыми, и т.д.

   Аналогично нулевые элементы можно ввести и в двух других рассмотренных ранее задачах. В задаче про последовательности из нулей и единиц большого смысла в этом нет, там как ни крути, а два особых случая нужны, но можно ради красоты понять, что ans[0]=1 (действительно, тогда ans[2] посчитается правильно - и логично, ведь есть только одна строка длины ноль - пустая строка), и тогда инициализировать только ans[1] и ans[0], а основной цикл писать от двух. В принципе, это, может быть, потом сыграет при выводе k-й по счету последовательности, но пока нам введение нулевого элемента здесь ничего не даёт.

   А вот в задаче про монеты очень естественно рассмотреть i=0. Не имея ни одной монеты, нельзя набрать ничего, кроме нуля, поэтому ans[0,0]=true, а остальные ans[0, j]=false и действительно, несложно проверить, что остальные элементы будут считаться правильно. Поэтому инициализируем нулевую строку массива и дальше основной цикл идёт с единицы,  а  не с двойки. Это не сильно упрощает алгоритм (будет одно присваивание в особых случаях, а не два), но для задания 2 про возможность использования одной монеты много раз введение нулевой строки уже поможет сильнее; также далее будет видно, что выводить само решение также проще, если ввести нулевую строку.

   2. Хранение только последних строк таблицы. Обычно подзадачи, которые мы решаем, характеризуются одним или несколькими индексами i, j, ... (хотя бы потому, что ответы надо хранить где-то в массиве). Нередко бывает так, что один (или несколько) из этих индексов (пусть i) таковы, что все ребра нашего графа подзадач идут между подзадачами, у которых i отличается ненамного. Т.е. задача с индексами  i, j, ... зависит только от задач с индексами i', j', ... такими, что i−q≤i'≤i, где q - не очень большое число. Например, в задаче про черепашку q=1: задача (i, j) зависит только от задач (i−1, j) и (i, j−1); аналогично в задаче про монеты задача (i, j) зависит только от задач (i−1, j') с некоторыми j'. В задаче про 01-последовательности задача i зависит только от i−1 и i−2.

   Нередко программу решения таких задач можно написать так, что самый внешний цикл будет циклом по тому же индексу i (именно так и написаны все примеры выше). В таком случае очевидно, что, если мы уже дошли в этом цикле до i=100, то нам скорее всего не надо помнить все насчитанные ранее значения; достаточно только помнить значения с i=100, i=99, ..., i=100−q; остальные нам никогда больше не понадобятся.

   Поэтому можно написать программу немного по-другому. Будем хранить ответы только на подзадачи с текущим i, а также на подзадачи с несколькими предыдущими i. Например, если  q=1 (т.е. задача i связана только с i−1), то будем хранить два массива, cur и old - ответы на подзадачи с текущим и предыдущим i соответственно (далее будем называть множество таких ответом строкой таблицы, хотя в общем случае, конечно, это может быть и одно число, и одномерный массив, и многомерный массив, в зависимости от того, сколько ещё индексов характеризует нашу задачу). В цикле будем вычислять все элементы cur, используя old и, при необходимости, уже насчитанные элементы cur, а потом сделаем old:=cur и перейдём на следующую итерацию цикла.

   Например, в задаче про черепашку с насчетом числа способов:

var cur,old:array[0..maxM] of integer; ... fillchar(old,sizeof(old),0); old[1]:=1; for i:=1 to N do begin     cur[0]:=0;     for j:=1 to M do         cur[j]:=cur[j1]+old[j];     old:=cur; end;

   Ответ лежит в cur[M] (и в old[M], конечно). Здесь мы уже ввёли нулевые элементы, как писалось выше. В цикле всегда (точнее, до последней строки) old[j] соответствует ans[i−1, j] в предыдущих реализациях, а cur[j]-ans[i, j]. По аналогии со сказанным выше, я инициализирую все нулевые элементы нулями, кроме ans[0,1], который теперь есть old[1] в начале программы (догадайтесь, почему именно ans[0,1], а не ans[1,0] :) ). Надеемся, что этот пример прояснил довольно мутные наши рассуждения, написанные выше.

   Задание 11: Напишите аналогично задачу про монеты.

   В ситуации, когда q>1, можно или завести несколько переменных, в которых хранить отдельные строки массива, а в конце цикла делать что-нибудь в стиле a:=b; b:=c; c:=d; ..., либо хранить последние q+1 строку (соответствующие i, i−1, i−2, ..., i−q) в массиве типа array[0..q, ...]. Можете додумать второй вариант сами, а первый способ продемонстрируем на примере задачи про 01-последовательности:

a:=1; b:=2; for i:=2 to n do begin     c:=a+b;     a:=b;     b:=c; end;

   Здесь c=ans[i], b=ans[i−1], a=ans[i−2].

   Зачем всё это нужно? В первую очередь для того, чтобы экономить память. Если вы, например, решаете задачу про монеты с N=S=10000, то в ограничение времени вы, скорее всего, уложитесь (сложность алгоритма O(NS), и константа невелика), но вам нужен будет массив порядка 10000×10000. На Borland Pascal вам никто столько не даст, да и на Delphi вы, скорее всего, в ограничение по  памяти не влезете. Если же вы напишите решение с сохранением только последних строк таблицы, то в память спокойно уложитесь.

   Правда, обычно всё не так плохо, и на Delphi памяти обычно хватает, поэтому эта идея намного чаще используется, если вы пишете на BP. Тем не менее все равно, даже если пишете на Delphi или на С++, полезно на всякий случай представлять себе, что такое бывает, и быть готовым применить этот приём.

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

fillchar(ans,sizeof(ans),false); ans[0]:=true; for i:=1 to n do     for j:=s downto a[i] do         ans[j]:=ans[j] or ans[ja[i]];

   Разберитесь, почему это работает (может быть, полезно вручную промоделировать), и почему цикл по j идёт от больших значений к меньшим. Обратите внимание на то, как мы избавились от if’а. Задание 12: Какую задачу будет решать этот же код, но с циклом по j  в обратном порядке, т.е. от a[i] до s?

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

   Кстати,  такому  коду,  пожалуй,  можно  даже  придумать  полноценное  ДПшное  оправдание.  Можете придумать :)

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

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

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

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

procedure out(i,j); begin    ...    if ans[i1,j]>ans[i,j1] then begin       out(i1,j);       write(’R’);    end else begin       out(i,j1);       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,j1);       write(’U’);       exit;    end;    if (j=1) then begin       out(i1,j);       write(’R’);       exit;    end;    if ans[i1,j]>ans[i,j1] then begin       out(i1,j);       write(’R’);    end else begin       out(i,j1);       write(’U’);    end; end;

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

   Задание 13: Напишите процедуру out для случая, когда мы ввели нулевые элементы массива так, как это было сказано в соответствующем разделе.
   А для задачи про монеты? Всё просто и совершенно аналогично. Будет процедура out(i, j), которая будет выводить способ набора суммы j с помощью первых i монет. Конечно, если такого способа не существует (т.е. ans[i, j]=false), то такой вызов бессмысленен - мы будем считать, что процедура out всегда будет вызываться с параметрами, для  которых решение существует. Тогда мы, ещё когда придумывали рекуррентное соотношение, поняли, что это решение либо включает монету a_i, либо не включает. Сейчас, когда мы уже насчитали всю матрицу ans, определить, какой из двух случаев имеет место, легко: если j≥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[i1,ja[i]]) then begin       out(i1,ja[i]);       write(i,’ ’);    end else        out(i1,j); end;

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

   Обратите ещё внимание на то, как автоматически получается, что мы никогда не вызываем out с параметрами, для которых нет решения. Действительно, если массив ans насчитан правильно и решение для (i, j) существует, то в соответствии с рекуррентной формулой оно существует или для  (i−1, j−a_i), или для  (i−1, j), причём первый вариант может иметь место только при j≥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 мы не вызываем.

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

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

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

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

   §3. Вывод лексикографически первого решения. Иногда бывает, что при  наличии нескольких решений требуют вывести какое-нибудь определённое, например, в некотором смысле лексикографически наименьшее. В общем случае это несколько меняет саму задачу и это приходится учитывать в рекуррентном соотношении. Например, если бы в задаче про монеты требовали вывести решение с наименьшим числом монет, то получилось бы задание 3, над которым, мы надеемся, вы уже подумали - там для соблюдения дополнительного условия приходится привлекать тяжёлую артиллерию, т.е. менять само рекуррентное соотношение, но зато в итоге вывод ответа опять становится элементарным. Но бывают случаи, когда можно обойтись лишь простым изменением процедуры out или небольшой коррекцией основного цикла вычисления массива ans. Например (пример какой-то неестественный получается, но ничего другого в голову с ходу не приходит), пусть нам нужно по возможность использовать монеты с большими номерами. А именно, если можно вывести решение с монетой a_N, то вывести его, иначе (никуда не денешься) без монеты a_N; среди всех таких решений по возможности выбрать решение с a_N−1, среди всех их с a_N−2 и т.д. Такой в некотором смысле аналог лексикографического порядка. Это требование элементарно удовлетворяется; на самом деле, если подумать, то приведённая выше процедура out именно это и делает: ведь, выводя решение out(i, j), надо, если можно, вывести решение, содержащее i-ю монету, и только если такого нет, то вывести решение без неё. Именно это мы и делаем. Если бы мы написали подругому:

procedure out(i,j) begin    if i=0 then exit;    if (ans[i1,j) then       out(i1,j);    else begin       out(i1,ja[i]);       write(i,’ ’);    end; end;

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

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

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

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

   Задание 15: Научитесь выводить первое в лексикографическим порядке решение задачи про черепашку с набором максимальной суммы. Решение задаём строкой из букв 'R' и 'U' и лексикографический порядок на этих строках определяем как всегда.
   §4. Нетривиальный пример: задача про наибольшую возрастающую подпоследователь ность. Дан массив  a₁, a₂, ..., a_N. Требуется вычеркнуть из него как можно меньше чисел так, чтобы получилась строго возрастающая последовательность.  (Конечно,  можно  потребовать  нестрого  возрастающую,  или убывающую - всё будет аналогично.) Например, для массива 1 3 3 1 4 2 решением будет оставить 1 3 4.

   Будем решать задачу динамическим программированием. На самом деле есть какой-то довольно простой способ решить задачу за O(N log N), но мы не будем мучиться и решим её за O(N²). Итак, для каждого i посчитаем длину наибольшей возрастающей подпоследовательности куска a₁, ..., a_i при условии, что a_i обязательно входит в эту последовательность, и запишем эту длину в ans[i]. Например, для приведённого выше примера массив ans должен будет иметь вид 1 2 2 1 3 2. Ясно, что мы считаем?
   Выбор подзадач кажется немного странным. Может захотеться реализовать ДП для тех подзадач, которые первыми приходят в голову: ans[i] будет длиной наибольшей возрастающей последовательности среди первых i чисел, но мы пока не знаем, как такие подзадачи свести к более мелким. Дело в том, что последовательность должна быть возрастающей, а потому при сведении к более мелким подзадачам нам важно как-то быть уверенными, что ответ на более мелкую подзадачу не закончится на слишком большое число - поэтому проще всего знать это самое число. Вообще, это довольно стандартный приём в задачах на выбор элементов потребовать, чтобы последний элемент обязательно входил.

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

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

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

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

   Ещё раз. Мы вычисляем максимум ans[j] по всем j таким, что 0≤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; ...

   Т.е. если мы нашли ещё один вариант с такой же длиной, то иногда имеет смысл перезаписать наше старое решение.
   Все, после этого будет выводиться нужное решение.
   §5. Пример на нетривиальную процедуру out: алгоритм Флойда с сохранением промежуточной вершины. Мы не будем подробно рассказывать здесь алгоритм Флойда, просто скажем, что он ищет кратчайшие пути между всеми парами вершин графа, при этом в одном из вариантов в массиве from в элементе from[i, j] хранит некоторую вершину, лежащую на  кратчайшем  пути из i в j (или -1, если кратчайший путь из i в j не проходит ни через какие другие вершины). Тогда процедуру 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, про которую мы говорили как-то выше: она теперь не делает рекурсивный вызов и потом что-то нерекурсивно выводит, а делает что-то более хитрое.
    Ещё тут есть тонкость, что такая процедура out не выводит последнюю вершину пути, иначе на стыке вершина from[i, j] была бы выведена дважды, но это сейчас не принципиальный момент.

Часть IV. Классы задач на ДП

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

   §1. Подсчёт объектов, в том числе определение существования объекта. Т.е. надо посчитать, сколько всего существует объектов с заданными свойствами, или проверить, существует ли хотя бы один. Примеры таких задач мы уже видели: первая задача про  черепашку, задача про 01-последовательности и задача про монеты. Мы думаем, более-менее понятно, как решаются подобные задачи.

   В такой задаче (особенно в задаче проверки существования объекта) могут попросить вывести пример объекта - мы уже обсуждали, как это делается.
   §2. Нахождение оптимального объекта. Требуется в некотором множестве объектов найти в некотором смысле оптимальный. Такую задачу мы тоже уже видели: вторая задача про черепашку. Здесь тоже могут попросить вывести это оптимальный объект, и вы уже знаете, как это сделать.
   §3. Вывод k-ого объекта. Но есть ещё один тип задач, который мы ещё не рассматривали. Могут попросить по данному k вывести k-ый в некотором порядке объект. Например, пусть в задаче про 01-последовательности нас не просто просят посчитать количество хороших последовательностей длины N, а просят вывести k-ую в лексикографическом порядке из них (конечно, гарантируя, что k не превосходит общего количества таких последовательностей).
   Как это сделать? На самом деле это делается легко и весьма похоже на вывод какой-нибудь хорошей последовательности, что по сути мы с вами уже обсуждали. (Мы уже даже обсуждали, что можно легко сделать так, чтобы выводился первый в лексикографическом порядке объект.) Поэтому давайте предварительно методом ДП посчитаем количество хороших последовательностей длины i для всех i от 1 до N (ну или от нуля, вам виднее). А дальше...
   А дальше раньше мы писали процедуру out(i), которая выводила любую хорошую последовательность длины i. Теперь нам надо выводить не какую попало, а вполне определённую - поэтому давайте напишем процедуру out(i, k), которая будет выводить k-ую в лексикографическом порядке последовательность среди всех хороших последовательностей длины i.
   Как это делать? Попробуем воспользоваться тем, что мы знаем, как выглядит любая хорошая последовательность длины i. Она либо заканчивается на 0, перед чем идёт хорошая последовательность длины i-1, либо на 01, перед чем идёт хорошая последовательность длины i-2. Мы разделили последовательности длины i на два типа, но это нам ничего не даёт, т.к. если все последовательности длины i записать в отсортированном порядке, то последовательности этих двух типов будут идти вперемешку. Может быть, тут можно будет найти закономерность, но мы поступим по-другому.
   Ясно, что нам бы хотелось так разбить последовательности длины i на группы, чтобы в отсортированном порядке шла сначала одна группа, а потом только другая. Но это же легко! Просто записывая рекуррентное соотношение, будем смотреть не на то, чем заканчивается последовательность, а на то, чем она начинается. Совершенно аналогично тому, как мы раньше решали эту задачу, здесь поймём, что хорошая последовательность длины i - это

1. либо 0, после чего идёт хорошая последовательность длины i-1,
2. либо 10, после чего идёт хорошая последовательность длины i-2,

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

   Теперь вспомним о нашей цели: написании процедуры out(i, k). Надо вывести k-ую последовательность в этом списке. Но тогда понятно, что если k≤ans[i-1], то ответ начинается на ноль, иначе на 10. Более того: ведь в пределах одной группы последовательности отсортированы в лексикографическом порядке, т.е. первая группа - это ноль, после которого идут последовательности длины i-1, причём тоже в лексикографическом порядке, и аналогично вторая группа! Поэтому k-ая последовательность длины i - это:  если k≤ans[i-1], то: '0', к которому приписана k-ая последовательность длины i-1; иначе (k>ans[i-1]): '10', к чему приписана (внимание!) (k-ans[i-1])-ая последовательность длины i-2. Это уже пишется легко; для вывода более коротких последовательностей, естественно, воспользуемся рекурсивным вызовом:

procedure out(i,k); begin    ...    if (k<=ans[i-1]) then begin       write(0);       out(i-1,k);    end else begin       write(10);       out(i-2,k-ans[i-1]);    end; end;

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

procedure out(i,k); begin    if (i=0) then exit; //тут обязательно k=1;       // единственная последовательность длины 0 --- пустая строка    if (i=1) then begin //тут k может быть 1 или 2       if (k=1) then write(0)       else write(1);       exit;    end;    if (k<=ans[i-1]) then begin       write(0);       out(i-1,k);    end else begin        write(10);        out(i-2,k-ans[i-1]);    end; end;

   Ещё раз напоминаем, что здесь подразумевается, что всегда 1≤k≤ans[i]. Подумайте, почему, если из внешней программы мы вызвали процедуру out правильно, то и при всех рекурсивных вызовах это свойство сохранится.
   Итак, как в общем случае выводить k-ый объект? Ну, во-первых, надо динамически посчитать их количество. При этом динамика у вас обычно основывается на разделении множества объектов на группы и суммировании их количества - так надо организовать динамику так, чтобы по номеру объекта можно было легко отнести его к одной из групп. Чаще всего это получается просто за счёт того, что в отсортированном порядке сначала идут все объекты первой группы, потом - второй и т.д.; нередко чтобы добиться этого, приходится рассматривать, с чего начинается решение, а не чем заканчивается, но обычно это делается примерно одинаково.(Кстати, может быть, что разбиение на группы будет делаться как-нибудь по-другому, например, по остатку от деления k на что-нибудь, но мы примеров таких задач не приводим). После этого легко пишется процедура out(i, k): вы определяете, какой группе принадлежит k-ый объект и в соответствии с этим выводите его, скорее всего пользуясь рекурсивным вызовом.

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

procedure out(i,k);    ...    for g:=1 to ng do       if k<=nans[g] then begin           ...           out(ii,k);           break;        end else k:=k-nans[g];

   Здесь (очень условно!) написано следующее. g - это номер очередной группы, ng - их общее количество, nans - количество решений в этой группе. В реальной программе у вас почти наверняка обозначения будут другие и даже способ организации цикла может быть другим. Но суть в следующем: мы перебираем группы в лексикографическом порядке и каждый раз уменьшаем k на числе объектов в очередной группе - k в итоге обозначает, какой по счету объект нам надо вывести, не считая тех, что мы уже пропустили. В очередной момент k станет ≤ nans[g], т.е. станет ясно, что ответ находится в этой группе - поэтому надо вывести k-ый объект из этой группы. (Точнее, сейчас, наверное, не ясно, но наткнётесь когда-нибудь на пример - и будет ясно.)
   §4. Определение номера по объекту. Задача, противоположная предыдущей: дан объект, определить его номер. Решается аналогично, рассмотрим опять для примера задачу про 01-последовательности. Как определить номер данной последовательности? Вспоминая, как мы находили последовательность по номеру, и применяя те же соображения, получаем следующее решение: если данная нам последовательность длины N начинается на 0, то ответ будет просто ответом для последовательности с откинутым этим нулём. Если же начинается на единицу, то нужно эту единицу и следующий за ней ноль откинуть, найти номер получившейся последовательности (естественно, среди последовательностей длины N-2), а потом к нему прибавить ans[N-1]. Додумайте эту идею сами.

   Мы надеемся, что на этом примере идея нахождения номера по объекту ясна.

   Задание 17: Напишите эту программу.

   Задание 18: Напишите программу определения номера по пути в задаче про черепашку с подсчётом числа путей.

Часть V. Способы написания ДП

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

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

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

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

   §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]: он у нас вычислен!

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

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

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

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

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

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

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

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

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

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

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

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

   Задание 19: Решите эту задачу.

   §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;

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

   Итак, у нас будет массив 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-ой вершины. Т.е. ещё раз: то, что мы написали и топсорт - это, фактически, одно и то же, и идеология у них одна и та же.

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

Часть VI. Виды задач на ДП

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

   §1. Линейное ДП. Ну, это довольно просто. Вы для каждого i считаете некоторую величину, используя ранее насчитанные ответы при меньших i. Пример - задача про 01-последовательности, которую мы уже обсуждали. Отметим тут только ещё одну особенность, которая на самом деле относится ко всем видам ДП. Бывают два случая: либо, как в задаче про 01-последовательности, вам просто дано N и просят посчитать ans[N], который ни от чего, кроме N, не зависит. А бывает, как в задаче про наибольшую возрастающую последовательность, что вам дают массив a, обычно длины N, и ответ существенно зависит от этого массива - короче говоря, вам или дают только размеры, или ещё какие-то данные линейного (квадратичного и т.п.) размера по N (M и т.д.). В последнем случае может возникнуть вопрос: а как мы будем считать ans[i] для промежуточных i? В большинстве случаев ясно, как: ans[i] будет ответом для первых i элементов массива a. Т.е. подзадача от полной задачи будет отличаться просто тем, что выкинули несколько последних элементов массива a, и все. Могут, конечно, быть особые случаи, когда это не так, но это уж слишком :).

   Задание 20: Задача 7 "Числа" с последней области.
   §2. Многомерное ДП. Ничуть не сложнее предыдущего, просто здесь для каждого i и j вычисляете ans[i, j], или аналогично с тремя и более параметрами; как правило, здесь i, j и т.д. действительно играют роль в том или ином смысле координат: или напрямую, как в задачах про черепашку, или в некотором другом, но тоже простом смысле. Итак, две таких задачи мы уже разобрали, обсудим ещё классическую задачу на многомерное ДП - задачу про наибольшую общую подпоследовательность.

   Итак, даны  две  строки, s₁ и s₂. Требуется из каждой из них вычеркнуть несколько (возможно, ноль) символов так, чтобы получились одинаковые строки, причём получившиеся  строки  должны  иметь  максимальную  длину.  Пример: если есть две последовательности: acbaaba и bcacb, то ответом будет bab или acb или cab и т.п.: любую из этих строк можно получить вычёркиванием нескольких символов из обеих данных строк, но никакая более длинная строка таким свойством не обладает.

   Как решать эту задачу? Первая основная идея ДП: придумаем себе подзадачи. Здесь в качестве подзадач естественно рассмотреть следующие: для каждого i и j посчитаем  ans[i, j] - длину наибольшей общей подпоследовательности у первых i символов первой строки и у первых j символов второй строки. Например, в приведённом выше примере ans[4,3]=2: это длина наибольшей общей подпоследовательности у строк acba и bca (эта общая подпоследовательность - ba или ca).

   Как найти ответ на подзадачу? Вторая основная идея ДП: посмотрим, на что может кончаться решение. Имея ввиду, что нам надо свести нашу подзадачу к более мелким, понятно, что есть два варианта. Если i-ая буква первой строки не равна j-ой букве второй, то ясно, что хотя бы одну из них (а, может быть, и две) мы должны вычеркнуть, и дальше решать задачу, когда одна из строк стала короче. Тогда

ans[i, j] = max(ans[i - 1, j], ans[i, j - 1], ans[i - 1, j- 1]).

   Если же эти две буквы совпадают, то ясно, что мы либо не вычёркиваем их, и тогда решение будет решением для  (i-1, j-1), к которому приписана одна буква, либо хотя бы одну из них вычёркиваем - короче говоря,

ans[i, j] = max(ans[i - 1, j - 1] + 1, ans[i - 1, j], ans[i, j - 1], ans[i - 1, j - 1]).

   На самом деле, если подумать, то можно упростить эти соотношения и окончательно получить

   Задание 21: Докажите эти соотношения (они не очевидны!)
   Далее все ясно. В двойном цикле вычисляем значения, все понятно. Отметим, что это как раз и есть многомерное ДП: можно легко записать одну строчку по вертикали, вторую по горизонтали и писать ans матрицей между ними, как показано в таблице справа.

   Да, ещё важный момент. "База" динамики. Несложно видеть, что в соответствии с нашим рекуррентным соотношением особыми случаями тут являются i=1 или j=1. Если подумать, то полезно ввести нулевые строку и столбец с ans[0, j]=ans[i, 0]=0, и все будет работать.

   Задание 22: Напишите процедуру out для вывода решения в этой задаче.

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

   Отметим ещё один момент, общий вообще для ДП. Нередко, получив задачу, похожую на другую, знакомую вам, задачу на ДП, хочется просто свести одну к другой, т.е. придумать решение первой задачи в виде "по входным данным для первой задачи получим какие-то входные данные для второй, потом решим вторую, потом по решению второй найдём решение для первой". Например, есть задача про наибольший подпалиндром, которую мы подробно обсудим в следующем разделе. Кратко: дана строка, требуется вычеркнуть из неё минимальное количество букв так, чтобы получился палиндром - строка, читающаяся одинаково как слева направо, так и справа налево. Правильное и простое решение этой задачи мы обсудим чуть позже, а пока скажем, что может захотеться свести её к только что разобранной нами задаче о наибольшей подпоследовательности. Действительно, пусть нам дана строка s. Возьмём s₁=s, а в качестве s₂ возьмём перевёрнутую s, т.е. строку s, записанную задом наперёд - и найдём наибольшую общую подпоследовательность для s₁ и s₂. Кажется, она и будет ответом на начальную задачу, т.е. наибольшим подпалиндромом для s... Но не очевидно. Очевидно, что каждый подпалиндром будет общей подпоследовательностью, но обратное неверно. Можно доказать, что среди наибольших общих подпоследовательностей всегда найдется палиндром, т.е. что длина палиндрома таким алгоритмом будет определена верно, но есть примеры, когда есть несколько наибольших общих подпоследовательностей, и не все из них являются палиндромами. Таким образом, есть опасность правильно найти длину, но вывести неправильный ответ.

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

   На самом деле это довольно важная идея!

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

   Задание 24: Придумайте контрпримеры к двум приведённым способам решения этой задачи.

   Задание 25: Решите задачу о наибольшей общей подпоследовательности трёх строк по аналогии с задачей для двух строк.

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

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

   §3. ДП на подотрезках. Итак, тут мы и рассмотрим задачу о наибольшем подпалиндроме. Это (или близкая к ней задача) - задача с межнара’2000, и это та задача, на которой хорошо понять суть ДП. Осенью 2000 года автору попалось в руки решение Михаила Баутина. Решение набирало максбалл и автор этих строк пытался понять, как эти пять строчек могут решать эту задачу?! Но потом вдруг в какой-то момент понял.

   Итак, как решается эта задача. Дана строка s, надо найти её наибольший подпалиндром. Попробуем показать, как можно  дойти  до  такого решения  (хотя как будет видно далее, окончательная идея - просто стандартная идея ДП на подотрезках, и поэтому можно и сразу догадаться, как решать).  Давайте попробуем выбрать такие подзадачи: для каждого i посчитаем ans[i] - длину наибольшего подпалиндрома первых i символов строки s. На что может заканчиваться такой палиндром? Ну, очевидно. Он либо содержит символ s[i], либо нет. Если не содержит, то все просто - ответ будет равен ans[i-1]. А если содержит?.. Хм. Не так все просто, как могло показаться сначала. Если содержит, то последний символ нашего палиндрома будет s[i], тогда первый символ палиндрома должен с ним совпадать. Тогда вроде надо бы найти, где первый раз такой символ входит в нашу строку - пусть это позиция j, т.е. s[j]=s[i], и раньше позиции j этот символ не встречался. Тогда это вхождение и будет первым символом искомого палиндрома, а оставшаяся часть безусловно будет максимальным подпалиндромом... только для строки s[j+1..i-1], т.е. для подстроки строки s, начинающейся с позиции j+1 и идущей до позиции i-1. Но мы для такой задачи ответа не знаем, это не есть одна из наших подзадач...

   Но тогда ясно, что нужно попробовать немного по-другому. Что-то типа рекуррентного соотношения вырисовывается, но для немного других подзадач. Ну давайте и последуем этой идее. Нам надо знать ответ для любой подстроки, а не только для подстрок, начинающихся с первой позиции строки s? Так давайте так и поступим!

   Итак, новые подзадачи: для каждого l и r такого, что l≤r, вычислим ans[l,r] - длину наибольшего подпалиндрома для строки s[l..r], т.е. подстроки нашей строки, начинающейся с позиции l и заканчивающейся позицией r. Ясно, что мы считаем? Если s='abcbdefba', то ans[4,8] будет хранить длину наибольшего подпалиндрома для строки 'bdefb' (которая равна 3, очевидно). Как вычислить ans[l,r]? Легко: посмотрим, на что может заканчиваться искомый палиндром. Мы ведь уже имеем общее представление о том, что надо делать. Палиндром либо содержит последний символ строки, т.е. символ s[r], либо нет. Если нет, то ans[l,r]=ans[l,r-1]. А если содержит? Ну вроде даже понятно: надо найти, где первый  раз  в  нашей  текущей  строке s[l..r] входит символ, равный s[r] - пусть это будет позиция j, и тогда ans[l,r]=ans[j+1,r-1]+2 (два, т.к. к палиндрому-ответу на задачу (j+1,r-1) мы дописали два одинаковых символа: s[j] слева и s[r] справа). Казалось бы, всё, но тут ещё возникает стандартная оптимизация, которая часто появляется и в других задачах на ДП. А именно, зачем нам явно искать такой символ j? Могут быть два варианта: либо j=l, либо j≠l. В последнем случае, очевидно, это обозначает, что символ s[l] в ответ не входит, и ответ будет равен ans[l+1,r] (напомним, что мы рассматриваем пока случай, когда в ответ входит символ  s[r]), во втором случае (j= l) получаем, что s[l]=s[r] и очевидно, что ответ равен s[l+1,r-1]+2.

   Постарайтесь осознать этот переход, почему и как так получилось, что от цикла поиска j мы избавились. Дополнительное замечание, которое может это объяснить: если j≠l, то при вычислении ans[l+1,r] мы бы нашли то же самое значение j, так что зачем его ещё раз искать - ясно, что ans[l,r] в таком случае так или иначе сведётся к ans[l+1,r].

   Итак, вроде рекуррентное соотношение вырисовалось. Давайте ещё раз для ясности:

   если s[l] = s[r], то ans[l, r] = 2 + ans[l + 1, r - 1],

   иначе есть два варианта: либо в ответ не входит символ s[r], либо он входит, но тогда не входит s[l]. Т.е. в этом случае ответ есть max(ans[l+1,r],ans[l,r+1]).

   Окончательно:

   Задание 26: На самом деле строго мы это ещё не доказали. Докажите.

   Обратите внимание на "базу" динамики. Мі рекомендуем рассмотреть в качестве базы ans[l,l]=1 и ans[l+1,l]=0 (второе соотношение - некоторый аналог "нулевой строки"; на него будут ссылаться значения ans[l,l+1], если s[l]=s[l+1]).

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

   Итак, общая концепция динамики на подотрезках. Есть некоторая последовательность, строка и т.п. Параметрами динамики будут являться l и r - левая и правая граница некоторого куска этой строки /последовательности/...; соответственно, эту подзадачу сводим к более мелким. Инициализация обычно происходит для случаев l=r или l=r-1. Обратим внимание на то, в каком порядке надо вычислять элементы (конечно, это относится к случаю, когда вы пишете динамику просмотром вперёд или назад, а не рекурсией с запоминанием результата). Иногда бывает так, что для вычисления можно просто организовать пару вложенных циклов по l и r типа

for l:=1 to n do    for r:=l+1 to n do {обратите внимание, что здесь r>l всегда}          вычислить элемент ans[l,r]

   Но в большинстве случаев так не получается, в том числе так не получится в нашей задаче про подпалиндром. Действительно, у нас подзадача (l,r) зависит от (l,r-1), (l+1,r) и (l+1,r-1), т.е. ответы на эти три подзадачи должны быть вычислены до вычисления (l,r). В приведённом же выше коде подзадачи (l+1,r) и (l+1,r-1) вычисляются позже (l, r).

   Но очевидно, как эту проблему обойти. Действительно, каждая задача у нас зависит только от задач с более коротким куском (задача (l,r) зависит от задач (l',r') таких, что r'-l'<r-l), и это почти всегда так в динамике на подотрезках. Поэтому организуем вычисления в порядке увеличения длины куска. У нас будут два вложенных цикла: внешний по длине куска len, внутренний - например, по позиции начала куска l. Соответствующее r будет равно l+len-1, т.е. получаем такой код:

for len:=1 to n do     for l:=1 to n-len+1 do begin {обратите внимание на аккуратное значение верхнего предела}          r:=l+len-1;          вычислить элемент ans[l,r]     end;

   Таким образом, всегда, когда мы доберёмся до задачи (l,r), все задачи, от которых она зависит, уже будут решены.

   Задание 27: Напишите решение задачи про максимальный подпалиндром.

   Задание 28: Важное задание! Напишите процедуру out вывода решения в этой задаче.

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

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

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

   §4. ДП по полной сумме. Это - скорее отдельное замечание, чем отдельный важный тип, но тем не менее заметьте, что иногда бывает так, что одним из параметров динамики мы назначаем некоторую "полную сумму". Например, в задаче про монеты одним из параметров динамики была сумма, которую мы пытаемся набрать.

   Ещё пример - дано N отрезков, требуется сгруппировать их в две группы так, чтобы суммарная длина в первой группе равнялась суммарной длине во второй группе. На самом деле это в точности задача про монеты, надо только определить, можно ли набрать сумму, равную половине общей суммы всех отрезков. Но обратите внимание, что аналогично (при соответствующих ограничениях, конечно) решается и задача о группировке в три группы с равной суммарной длиной, и на четыре и т.д. Например, чтобы разбить на пять групп, можно придумать динамику за O(NL⁴): для каждых l₁, l₂, l₃, l₄ и i определим, можно ли сгруппировать первые i отрезков в 5 групп так, чтобы суммарная длина первой равнялась l₁, ..., четвёртой - l₄ (а пятой - сколько останется). Переход очевиден: чтобы определить, можно ли так сделать, переберём, в какую группу встаёт i-ый отрезок и посмотрим на соответствующий ответ для i-1. (Может быть, эту задачу можно и проще решать, но с ходу такое решение придумать трудно.)

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

   Задание 30: Есть N вещей, у каждой из которых известен вес и стоимость. Мы можем унести произвольный набор вещей при условии, что их суммарный вес не превосходит некоторого числа W. Требуется среди всех таких наборов выбрать набор с  максимальной суммарной стоимостью. Решите эту задачу за O(NW): найдите ответ и выведите само решение.

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

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

   Рекурсия с запоминанием результата пишется легко, прямо по шаблону поиска в глубину; для пометки, в каких вершинах были, не заводим отдельный массив, а используем массив ans (обратите внимание, что наш граф тут отличается от графа подзадач: в соответствии с тем, как мы выше определили граф подзадач, в нём ребра идут в другую сторону):

function find(u):integer; var max,t,v... begin    if ans[u]<>-1 then begin       find:=ans[u];       exit;    end;    max:=-1;    for v:=1 to n do       if gr[v,u]<>0 then begin {если из v в u идет ребро}          t:=find(v);          if t>max then             max:=t;       end;    ans[u]:=max+1;    find:=ans[u]; end;

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

   Ещё обратите внимание, что тут в коде нет уже привычных нам особых случаев - "базы" динамики (по аналогии с базой индукции). У нас всегда были совсем простые задачи, для которых мы ответ считали отдельно вручную и появлялись if’ы, а тут все получилось автоматически, т.к. "база" ДП - это те вершины, в которые не входят ребра, и все просто. Именно для этого случая max проинициализирована значением -1.

   Задание 31: Напишите процедуру out вывода решения в этой задаче.

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

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

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

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

   Если дерево задано как-нибудь неудобно, то ничего лучше, чем в прошлом разделе, вы, наверное, не придумаете (ну и не страшно! решение, написанное как в прошлом разделе, будет работать столь же хорошо). Но пусть дерево задано так, как мы только что описали. Тогда тут легко пишется динамика с просмотром вперёд:

fillchar(ans,sizeof(ans),0); for i:=n downto 2 do     if ans[i]+1>ans[p[i]] then        ans[p[i]]:=ans[i]+1;

здесь p[i] - родитель вершины i.

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

   Кстати, это доказательство того, что ДП с просмотром вперёд не всегда заменяется "обращением" динамики, как в решении 19.

   Задание 32: Дано дерево. Найдите в нем наибольшее паросочетание, т.е. набор рёбер такой, что 1) никакие два ребра не имеют общего конца, 2) число рёбер максимально возможно. Напишите как само ДП, так и процедуру out вывода решения.

   §7. Игры. В отличие от остальных подпунктов в этом разделе это, конечно, не совсем особый вид задач на ДП, и не особый приём реализации ДП. Это, скорее, класс задач, которые стандартным образом сводятся к ДП, но мы его решили рассказать здесь, т.к. довольно логично его рассказывать после динамики на ациклических графах.

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

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

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

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

   Итак, позицию назовём выигрышной, если тот, кто из неё ходит, выигрывает при правильной игре, иначе проигрышной. Тип каждой позиции однозначно и достаточно легко зависит от типов тех позиций, в которые из неё можно пойти. Действительно, если из позиции u есть ход в какую-нибудь проигрышную позицию v, то, очевидно, u - выигрышная позиция, и для победы при нашем ходе из позиции u нам надо просто сходит в позицию v. Оттуда будет ходить наш противник, и он проиграет, т.к. v проигрышная - значит, мы выиграем. А вот если из позиции u нет ходов в проигрышные позиции, т.е. все ходы из неё - в выигрышные, то нам деваться некуда: куда мы не пойдём, противник выиграет. Значит, u - проигрышная позиция.

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

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

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

   Пример. В куче лежит N камней. За один ход каждый игрок может взять от 1 до M камней. Проигрывает тот, кто не может сделать ход. Дано N и M, определите, кто выигрывает при правильной игре.

   В этой задаче есть элементарная закономерность и, может быть, вы даже её знаете. Но мы не будем её искать, а будет писать динамическое решение. В массиве ans храним тип позиции: ans[i]=1, если позиция i (т.е. куча с i камнями) выигрышна, и ans[i]=2, если проигрышна. ans[0]=2 по условию (осознайте это!). Динамика пишется легко:

ans[0]:=2; for i:=1 to n do begin     ans[i]:=2;     for j:=1 to m do         if (j<=i) and (ans[i-j]=2) then            ans[i]:=1; end;

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

   Ещё пример. То же самое, но каждым ходом можно брать не больше, чем предыдущим ходом взял противник. Здесь позиция уже однозначно не определяется количеством камней в куче, надо ещё и хранить, сколько предыдущим ходом взял противник. Т.е. позиция будет (i,j): i камней в куче и первым ходом можно взять не более j камней. Додумайте.

   Задание 33: Додумайте эту задачу.

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

   Такой вид задач также решается динамикой, только теперь для каждой позиции считаем, сколько максимум выигрывает игрок, ходящий из этой позиции. Определяем это легко: перебираем все возможные ходы. Пусть за некоторый ход мы должны заплатить противнику сумму a, и при этом мы уже знаем, что ответ для той позиции, куда ведёт этот ход, равен b (как a, так и b может быть и положительным, и отрицательным, конечно). Тогда если мы изберём этот ход, то противник сразу получит сумму a, а потом, играя из той позиции, куда мы попали, он получит ещё b, т.е. общий доход противника будет a+b, значит, наш доход будет (-a-b). Выбрав максимум по всем ходам, мы найдём ответ для текущей позиции. Мы не будем приводить примера задачи, но подумайте и попробуйте придумать пример сами :)

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

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

   Иногда бывает так, что игроки в каком-то смысле несимметричны. Например, игроки ходят не по очереди, а для каждой позиции задано, кто из неё ходит: из некоторых позиций ходит всегда Вова, из некоторых - Юра. Тогда все аналогично, только удобнее ответ определять не для "текущего" игрока, а, например, для Вовы (т.е.: если начать играть из этой позиции, то выиграет ли Вова? или: если начать из этой позиции, то какую максимальную сумму заработает Вова?)

   Аналогичная идея - в следующей задаче.

   Задание 34: В кучке лежат N камешков. Двое игроков ходят по очереди. Первый своим ходом может взять из кучи от 3 до 5 камешков, второй - добавить в кучу 1 или 2 камешка. Выигрывает тот, после чьего хода камешков в куче не останется или количество камешков в куче будет делиться на 30, либо после чьего хода противник не сможет сходить. Кто выигрывает при правильной игре? (Может так оказаться, что тут есть простая закономерность, например, всегда выигрывает второй - мы об этом пока не говорим. Но в любом случае придумайте динамическое решение за O(N).)

   §8. ДП на подмножествах. Ещё одна полезная идея ДП бывает следующая. Пусть нам дано некоторое множество объектов. Давайте одним из параметров динамики будет подмножество этого множества, т.е. в простейшем варианте просто посчитаем то, что нам надо, для каждого подмножества этого множества (в более сложном варианте, конечно, могут быть дополнительные параметры у динамики). Конечно, таких подмножеств будет 2ⁿ, где n - количество таких объектов, и потому при больших n ничего не получится, но при n до 20 и даже немного больше вполне сойдёт. (Кстати, если у вас в задаче есть ограничение типа n≤18, то тут можно сразу заподозрить алгоритмы с асимптотикой типа 2ⁿ, в том числе, и динамику по подмножествам)

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

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

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

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

   Как это писать? Подмножество будем кодировать двоичных числом, в котором i-ый бит равен единице, если i-ая вершина входит в подмножество, и нулю, если нет. При этом вершины приходится нумеровать с нуля, а подмножества будут кодироваться числами от 0 до 2^N-1. Обратите внимание, что если множество A является подмножеством B, то номер A строго меньше, чем номер B. Вполне естественно, что во всех задачах на динамику по подмножествам ответ на данное множество зависит только от ответов на его подмножества, поэтому цикл

for i:=0 to (1 shl N) -1

для любой (ну ладно, для любой нормальной) ДП по подмножествам перебирает подмножества уже в оттопсорченном порядке.

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

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

for i:=0 to (1 shl N)-1 do begin     ans[i]:=0;     for j:=0 to N-1 do {перебираем вершины: они занумерованы от 0 до N-1}          if (i and (1 shl j)<>0) then begin {если вершина j лежит в нашем множестве}             t:=ans[i and (not (1 shl j))];    {попробуем ее выкинуть...}             ans[i]:=t;      {...и посмотреть ответ для того, что получится}              {или переберем, какая вершина может быть парной к j-ой:                она тоже должна лежать в нашем множестве и быть связана с j ребром}             for k:=j+1 to N-1 do if (i and (1 shl k)<>0) and (gr[j,k]<>0) then begin                 t:=ans[i and (not (1 shl j)) and (not (1 shl k))];     {выкинем их обе и посмотрим ответ}                 if t+1>ans[i] then                    ans[i]:=t+1;             end;             break; {нам достаточно обработать только одну вершину из множества}          end; end;

   i and (1 shl j)<>0 проверяет, лежит ли вершина j в множестве i; i and (not (1 shl j)) даёт номер множества, получающегося из множества i выкидыванием вершины j, и т.д.

   Ещё раз про то, зачем тут break. Нам ведь надо взять какую-нибудь вершину из нашего множества и далее работать с ней (т.е. попробовать её выкинуть или найти  ей пару), но по номеру множества найти какую-нибудь вершину, лежащую в нем, сложно (точнее, легко, например, что-нибудь типа ((i-1) and (not i))+1, но мы решили не грузить вас ещё битовой арифметикой, да это ещё и для нуля работать не будет), поэтому и написан такой цикл с break.

   Задание 35: Напишите процедуру out вывода решения в этой задаче.

   В  общем, мы надеемся, идея динамики по подмножествам вам понятна. Помимо самой идеи, тут ещё важна нумерация множеств, тот факт, что цикл от 0 до 2^N-1 все решает, и тот факт, что многие действия делаются битовой арифметикой, в том числе - важное действие - проверка, лежит ли элемент j в множестве i.

   Ещё отметм, что тут требуется O(2ⁿ) памяти. На BP это может представить проблему.

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

   §9. ДП по профилю. Считается, видимо, самой страшной темой, хотя, как во всей динамике, ничего страшного тут, если разобраться и прочувствовать. Идея обычно такая: пусть имеется поле размера N×M, при этом N может быть велико, зато M обычно очень мало. Надо с этим полем что-то сделать: покрасить, расставить на нем королей и т.п. ДП по профилю состоит в следующем: назовём  профилем решение или
т.п. (раскраску, расстановку королей и т.п.) для поля 1×M [в более сложных задачах может потребоваться поле 2×M и т.п., и профиль будет не обязательно решение, а что-то ещё... В общем, в общем случае надо думать головой :), но основная идея от этого не изменится] И теперь основная идея: за счёт того, что M невелико, всевозможных профилей будет не слишком много, а потому мы сможем сделать следующее. Для каждого i и для каждого профиля p решим нашу задачу для поля i×M при условии, что последняя строка решения (раскраски, расстановки, ...) будет совпадать с профилем p. (Мы считаем, что размер поля - i по вертикали, M по горизонтали и в этом смысле и говорим о строке. Можно было считать, что i по горизонтали, M по вертикали, и требовать, чтобы последний столбец совпадал с профилем p.) В более сложных задачах, конечно, может быть хитрее.

   Но давайте лучше рассмотрим пример. Классическая задача на ДП по профилю - симпатичные узоры. Рассмотрим клеточное поле N×M. Раскрасим его клетки в белый и чёрный цвета. Назовём полученную раскраску - узор - симпатичным, если нигде внутри него не встречается однотонного квадрата 2×2. Т.е. в любом квадрате 2×2 хотя бы одна клетка белая и хотя бы одна клетка чёрная. Даны N, M, требуется найти количество симпатичных узоров размера N×M.

   Будем считать, что M невелико (очень невелико, так, что мы можем позволить себе работать за O(N-4^M ) и можем позволить выделить в памяти двумерный массив N×2^M). Решим эту задачу динамикой по профилю.

   Профилем назовём раскраску в белый и чёрный цвета строки 1×M; всего разных профилей, очевидно, будет 2^M (пока о симпатичности не говорим). Теперь, для каждого i (1≤i≤N) и для каждого профиля p решим следующую задачу: определить количество симпатичных узоров размера i×M при условии, что их последняя строка является профилем p. Точнее. Профили, конечно, будем нумеровать от 0 до 2^M-1. Пусть ans[i,j] есть количество симпатичных узоров размера i×M таких, что их последняя строчка есть профиль с номером j. Как вычислять ans[i,j]? Легко. При i=1, очевидно, ans[1, j]=1 для любого j: последняя и единственная строка строго фиксирована, о симпатичности речи пока нет, т.к. все узоры размера 1×M симпатичны: там просто нет квадратов 2×2.

   Пусть теперь i>1. Попробуем свести задачу (i,j) к задачам с меньшим i. Легко. Последняя строка нашего узора фиксирована, а какой может быть предпоследняя строка? Ясно, что это тоже будет некоторый профиль с номером k такой, что в последних двух строках нет однотонных квадратов 2×2 (т.е. профиль k может идти перед профилем j тогда и только тогда, когда если пририсовать профиль j под профилем k, получив прямоугольник 2×M, то он будет симпатичным). Более того, ясно, что если k может идти перед j, то узоров, в которых последняя строка j, а предпоследняя строка k, будет ровно ans[i-1,k]. Ура!

сумма берётся по всем профилям k таким, что профиль j может идти после профиля k.

   Ответом на задачу теперь будет просто сумма по всем профилям ans[N,i]:

   Как и было обещано, решение работает за O(N·2^M·2^M) и требует O(N·2^M) памяти.

   Эта задача была на первой Всероссийской олимпиаде школьников по командному программированию. Команда, в который был и автор статьи, тогда решила её с третьей попытки; алгоритм, видимо, придумал Сергей Политов. Вот его реализация:

const inputFile=’input.txt’;       OutputFile=’output.txt’; var   a: array[0..31] of String;   q, r: array[0..31] of Longint;   t: array[0..31, 0..31] of Byte;   n, m, c: Integer; function Bin(a: Byte): String; var   s: String[6];   i: Byte; begin   i:= 1; s[0]:= #0;   while i<1 shl n do   begin     if a and i=0 then s:= #48+s else s:= #49+s;     Inc(i, i);   end;   Bin:= s; end; function Can(s1, s2: String): Byte; var   i: Byte;   l: Byte absolute s1; begin   Can:= 0;   for i:= 1 to l-1 do     if(s1[i]=s1[i+1])and(s1[i]=s2[i])and(s1[i]=s2[i+1])       then Exit;   Can:= 1;  end; procedure init; var   i: Byte; begin   assign(input,InputFile);reset(input);   Readln(n, m);   if m<n then begin i:= m; m:= n; n:= i; end;   close(input);

end; procedure solve; var   i, j, w: Byte;   g: Integer; begin   c:= 1 shl n;   for i:= 0 to c-1 do a[i]:= Bin(i); { (1) }   for i:= 0 to c-1 do                 { (2) }   for j:= i to c-1 do begin     w:= Can(a[i], a[j]); t[i, j]:=w;t[j,i]:=w;   end;   for i:= 0 to c-1 do q[i]:= 1;   for g:= 0 to m-2 do   { (3) }   begin     for i:= 0 to c-1 do     begin       r[i]:= 0;       for j:= 0 to c-1 do Inc(r[i],q[j]*t[i,j]); {(4)}     end;     q:= r;   { (5) }   end; end; procedure print; var   sm: Longint;   i: Byte; begin  assign(output,OutputFile);rewrite(output);   sm:= 0; for i:= 0 to c-1 do Inc(sm, q[i]);   Writeln(sm);   close(output); end; begin   init;   solve;   print; end.

    Написано несколько своеобразно, но вполне хорошо и красиво. Обозначения здесь другие, чем в нашем изложении выше, в частности, N и M поменяны местами (т.е. профилей теперь 2^N и т.д.).

   Функция Bin переводит номер профиля в строку; функция Can определяет, может ли один профиль идти за другим, и возвращает 1, если да, и 0, если нет. Процедура solve содержит собственно алгоритм. Сначала (1) насчитываем строки по профилям, потом (цикл (2)) насчитываем матрицу t: t[i,j] равно единице, если профиль j может следовать за профилем i (заметьте, что, очевидно, t[i,j]=t[j,i]). Ограничение было, видимо, M≤5, и потому все массивы до 31.

   А далее... Собственно основной цикл ДП - цикл (3). Вы ещё не удивились, что обещанного массива N×2^M нет? Это то, о чем мы говорили в конце раздела II: что нередко достаточно сохранять не весь массив ответов, а лишь пару его последних строк. Здесь ответы для текущей строки зависят лишь от ответов для предыдущей строки, поэтому можно хранить лишь ответы для текущей и предыдущей строки (номер текущей строки здесь равен, видимо,  g+2: g идёт от 0 до m-2, а номер строки должен идти от 2 до m). В q хранится ответ для предыдущей строки: q[j] равно количеству симпатичных узоров размера M×(g+1) с профилем j в конце; - а в r насчитывается ответ для текущей строки: r[i] есть количество симпатичных узоров размера M×(g+2) с профилем i в конце. В основном цикле (3) для обработки очередной строки надо насчитать все r[i], для этого цикл по i. В нём делаем суммирование в соответствии с нашей рекурсивной формулой - цикл (4). Обратите внимание, как получается, что за счёт того, что t[i,j] равно 1 или 0, мы либо добавляем q[j] к r[i], либо нет. После того, как вычислили r[i] для всех i, переходим к следующему g, и надо выполнить q:=r (5).

   Процедура print вычисляет окончательный ответ и выводит его.

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

   Надеемся, что идеей динамики по профилю вы прониклись.

   Задание 38: Сколько  есть способов расставить королей на доске N×M так, чтобы никто из них никого не бил? Не знаю, вдруг тут есть формула, но решите эту задачу динамикой по профилю. Тогда вы сможете решить и такую задачу: на доске N×M несколько клеток вырезаны. Сколькими способами на оставшихся клетках можно расставить королей, чтобы никто никого не бил?

   §10. Динамика по изломанному профилю. Ну, это совсем высший пилотаж. Если  вы что-то не поняли выше, то лучше разберитесь в том, что там не поняли. Если же все понимаете и прониклись, то рассматривайте этот раздел как материал к размышлению.

   ДП по изломанному профилю позволяет, например, решить задачу про симпатичные узоры за типа O(NM·2^M), т.е. теперь тут не 4^M, а 2^M. Расписывать его вам тут не  будем, кратко идея вот в чём: для каждого i и j рассмотрим доску, имеющую следующую  форму: это прямоугольник (i+1)×M, из последней ((i+1)-ой) строки которой удалены правые M-j клеток (т.е. левые j сохранены). Для каждого i, j и p определим количество симпатичных узоров для такой доски при условии, что нижние клетки всех M столбцов образую профиль p (т.е. профиль теперь частично в i-ой строке, а частично - в (i+1)-ой). Задача в общем случае сводится к (i, j-1, p'), а при j=0 - к (i-1,M,p).

   Если вы уже мастера ДП, то подумайте над тем, что тут написано и, наверное, вы сразу поймёте, в чем суть и даже, может быть, сможете написать.

Часть VII. Дополнительные задачи

   Задание 39: Найти число способов разложить данное число N в сумму слагаемых: а) считая разложения, различающиеся порядком слагаемых, различными; б) считая разложения, различающиеся порядком слагаемых, одинаковыми; в) считая разложения, различающиеся порядком слагаемых, одинаковыми и требуя, чтобы все слагаемые в каждом  разложении были различны; г) и т.п.

   Задание 40: Найти число правильных скобочных последовательностей, состоящих из N пар скобок. [Коротко говоря, правильная скобочная последовательность - это последовательность открывающих и закрывающих скобок, в которой скобки сбалансированы. (()) - это правильная скобочная последовательность из двух пар скобок, ()() - тоже, а )()( и ())( - нет. Мы надеемся, смысл определения понятен]. а) Используя только круглые скобки; б) используя круглые, квадратные и фигурные скобки: ()[], [{}] - правильные, а ({)} и )()( - нет.

   Научитесь выводить скобочную последовательность по номеру.

   Задание 41: Сколькими способами можно замостить доску N×M  доминошками?

   Задание 42: Дана строка s, состоящая из букв, и маска m. Маска может содержать буквы,  символы '*' и '?'. Звёздочка может обозначать любую строку (в т.ч. пустую), а знак вопроса - любой символ. Подходит ли данная строка под эту маску?

   И ещё мы дадим несколько задач, по которым мы почти не будем писать ответы/подсказки/ и т.п.; в разделе "Ответы" вы найдёте только скорее комментарии по их использованию. Думайте над этими задачами сами :)

   Задание 43: При умножении матрицы размера a×b на матрицу b×c получается матрица a×c, при этом требуется abc умножений чисел. Умножение матриц не коммутативно (т.е. матрицы нельзя менять местами: AB≠BA), но ассоциативно (т.е. в любом выражении можно расставлять скобки как угодно, результат от этого не изменится: A(BC)=(AB)C). Правда, от расстановки скобок в выражении зависит количество необходимых умножений чисел. Соответственно, получается задача. Дано выражение A₁·A₂·...A_n, где A₁, A₂ и т.д. - матрицы; размер матрицы A_i - r_i×c_i, при этом c_i=r_i+1 для всех i. Требуется в выражении расставить скобки (т.е. указать порядок выполнения действий) так, чтобы потребовалось как можно меньше умножений чисел.

   Задание 44: Дана строка s₁. Разрешается за одно действие либо удалить произвольный символ текущей строки, либо вставить произвольный символ в произвольное место текущей строки, либо изменить произвольный символ текущей строки (на любой символ по вашему выбору). а) Требуется за наименьшее число действий получить данную строку s₂. б) То же самое, но за каждое  действие есть штраф: d за удаление, i за вставку и c за замену, требуется минимизировать штраф. в) То же самое, но штрафы зависят от того, что это за символы (т.е. штраф за удаление зависит от того, какой символ удаляем и т.д.; все эти зависимости заданы во входном файле). г) и т.д.

T_EX’s line-breaking algorithm has proved to be general enough to

handle a surprising variety of di?erent applications; this, in fact, is

probably the most interesting aspect of the whole T_EX system.
Donald E. Knuth. The T_EXbook

Вы не ужасайтесь... реально все тривиально...

Часть VIII. Условия всех задач

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

   Контрольный вопрос 1 (стр. 1): Как найти ответы на эти подзадачи?

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

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

   Задание 4 (стр. 6): Попробуем, как и раньше, в качестве подзадач рассматривать задачу поиска оптимального пути от (1,1) до (i,j) для всех i и j. Поймите, почему принцип оптимальности для подзадач тут не будет выполнен, и, соответственно, почему нельзя решить эту задачу напрямую аналогично обычной задаче про черепашку.

   Задание 5 (стр. 6): Придумайте, какие подзадачи тут можно рассмотреть, чтобы принцип оптимальности выполнялся, и решите-таки эту задачу методом ДП.

   Задание 6 (стр. 6): Решите эту задачу.

   Задание 7 (стр. 6): Зачем нужны эти три условия?

   Задание 8 (стр. 6): Поймите, почему тут не работает принцип оптимальности, почему эта задача не решается тупой динамикой и как одно связано с другим.

   Задание 9 (стр. 6): Вспомните задачу про монеты. Там тоже каждой монетой можно было пользоваться не более одного раза, но при этом задача благополучно решалась динамикой. Чем таким наша задача отличается от задачи про монеты? Можете ли придумать какую-нибудь задачу, которая казалась бы близкой к нашей задаче про черепашку, но решалась бы динамикой аналогично задаче про монеты?

   Контрольный вопрос 10 (стр. 7): Понимаете ли вы, что остальные элементы в этих примерах считаются корректно?

   Задание 11 (стр. 8): Напишите аналогично задачу про монеты.

   Задание 12 (стр. 8): Какую задачу будет решать этот же код, но с циклом по j в обратном порядке, т.е. от a[i] до s?

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

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

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

   Задание 16 (стр. 15): Научитесь выводить k-ый в лексикографическом порядке путь черепашки в задаче с подсчётом количества путей.

   Задание 17 (стр. 15): Напишите эту программу.

   Задание 18 (стр. 16): Напишите программу определения номера по пути в задаче про черепашку с подсчётом числа путей.

   Задание 19 (стр. 17): Решите эту задачу.

   Задание 20 (стр. 19): Задача "Числа" с последней области.

   Задание 21 (стр. 19): Докажите эти соотношения (они не очевидны!)

   Задание 22 (стр. 19): Напишите процедуру out для вывода решения в этой задаче.

   Задание 23 (стр. 20): Подумайте над тем, как тут выводить первое в лексикографическом порядке решение. Нам кажется, это не очень тривиально.

   Задание 24 (стр. 20): Придумайте контрпримеры к двум приведённым способам решения этой задачи

   Задание 25 (стр. 20): Решите задачу о наибольшей общей подпоследовательности трёх строк по аналогии с задачей для двух строк.

   Задание 26 (стр. 21): На самом деле строго мы это ещё не доказали. Докажите.

   Задание 27 (стр. 22): Напишите решение задачи про максимальный подпалиндром.

   Задание 28 (стр. 22): Важное задание! Напишите процедуру out вывода решения в этой задаче.

   Задание 29 (стр. 22): Научитесь выводить первое в лексикографическом порядке решение здесь.

   Задание 30 (стр. 22): Есть N вещей, у каждой из которых известен вес и стоимость. Мы можем унести произвольный набор вещей при условии, что их суммарный вес не превосходит некоторого числа W. Требуется среди всех таких наборов выбрать набор с максимальной суммарной стоимостью. Решите эту задачу за O(NW): найдите ответ и выведите само решение.

   Задание 31 (стр. 23): Напишите процедуру out вывода решения в этой задаче.

   Задание 32 (стр. 23): Дано дерево. Найдите в нем наибольшее паросочетание, т.е. набор рёбер такой, что 1) никакие два ребра не имеют общего конца, 2) число рёбер максимально возможно. Напишите как само ДП, так и процедуру out вывода решения.

   Задание 33 (стр. 24): Додумайте эту задачу.

   Задание 34 (стр. 25): В кучке лежат N камешков. Двое игроков ходят по очереди. Первый своим ходом может взять из кучи от 3 до 5 камешков, второй - добавить в кучу 1 или 2 камешка. Выигрывает тот, после чьего хода камешков в куче не останется или количество камешков в куче будет делиться на 30, либо после чьего хода противник не сможет сходить. Кто выигрывает при правильной игре? (Может так оказаться, что тут есть простая закономерность, например, всегда выигрывает второй, пока не известно. Но в любом случае придумайте динамическое решение за O(N).)

   Задание 35 (стр. 26): Напишите процедуру out вывода решения в этой задаче.

   Задание 36 (стр. 26): Задача про перестановки с области. На самом деле это - отличная задача на теорию ДП. Вам потребуется, во-первых, динамика по подмножествам, во-вторых, умение по объекту находить номер. Обратите внимание, что ДП по подмножествам потребует тут ещё одного параметра, кроме самого подмножества, но зато обойдётся без этих мучений с поиском какого-нибудь элемента множества.

   Задание 37 (стр. 28): Научитесь выводить симпатичный узор по номеру. Т.е. придумайте, в каком порядке симпатичные узоры можно занумеровать так, чтобы вы смогли по номеру вывести узор, и научитесь это делать.

   Задание 38 (стр. 28): Сколько есть способов расставить королей на доске N×M так, чтобы никто из них никого не бил? Не знаем, вдруг тут есть формула, но решите эту задачу динамикой по профилю. Тогда вы сможете решить и такую задачу: на доске N×M несколько клеток вырезаны. Сколькими способами на оставшихся клетках можно расставить королей, чтобы никто никого не бил?

   Задание 39 (стр. 28): Найти число способов разложить данное число N в сумму слагаемых: а) считая разложения, различающиеся порядком слагаемых, различными; б) считая разложения, различающиеся порядком слагаемых, одинаковыми; в) считая разложения, различающиеся порядком слагаемых, одинаковыми и требуя, чтобы все слагаемые в каждом разложении были различны; г) и т.п.

   Задание 40 (стр. 28): Найти число правильных скобочных последовательностей, состоящих из N пар скобок. [Коротко говоря, правильная скобочная последовательность - это последовательность открывающих и закрывающих скобок, в которой скобки сбалансированы. (()) - это правильная скобочная последовательность из двух пар скобок, ()() - тоже, а )()( и ())( - нет. Надеемся, что смысл определения понятен]. а) Используя только круглые скобки; б) используя круглые, квадратные и фигурные скобки: ()[], [{}] - правильные, а ({)} и )()( - нет. Научитесь выводить скобочную последовательность по номеру.

   Задание 41 (стр. 28): Сколькими способами можно замостить доску N×M доминошками?

   Задание 42 (стр. 28): Дана строка s, состоящая из букв, и маска m. Маска может содержать буквы, символы '*' и '?'. Звёздочка может обозначать любую строку (в т.ч. пустую), а знак вопроса - любой символ. Подходит ли данная строка под эту маску?

   Задание 43 (стр. 28): При умножении матрицы размера a×b на матрицу b×c получается матрица a×c, при этом требуется abc умножений чисел. Умножение матриц не коммутативно (т.е. матрицы нельзя менять местами: AB≠BA), но ассоциативно (т.е. в любом выражении можно расставлять скобки как угодно, результат от этого не изменится: A(BC)=(AB)C). Правда, от расстановки скобок в выражении зависит количество необходимых умножений чисел. Соответственно, получается задача. Дано выражение A₁·A₂·...A_n, где A₁, A₂ и т.д. - матрицы; размер матрицы A_i - r_i×c_i, при этом c_i=r_i+1 для всех i. Требуется в выражении расставить скобки (т.е. указать порядок выполнения действий) так, чтобы потребовалось как можно меньше умножений чисел.

   Задание 44 (стр. 29): Дана строка s₁. Разрешается за одно действие либо удалить произвольный символ текущей строки, либо вставить произвольный символ в произвольное место текущей строки, либо изменить произвольный символ текущей строки (на любой символ по вашему выбору). а) Требуется за наименьшее число действий получить данную строку s₂. б) То же самое, но за каждое действие есть штраф: d за удаление, i за вставку и c за замену, требуется минимизировать штраф. в) То же самое, но штрафы зависят от того, что это за символы (т.е. штраф за  удаление зависит от того, какой символ удаляем и т.д.; все эти зависимости заданы во входном файле). г) и т.д.

   Задание 45 (стр. 29): Задание про форматирование абзаца.

(Продолжение следует...)