О связи перебора и ДП, или Как переборные решения превращать в ДП

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

Пример: последовательности из нулей и единиц

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

var ans:integer;
    a:array[1..100] of integer;
    n:integer;

procedure check;
begin
inc(ans);
end;

procedure find(i:integer);
begin
if i>n then begin
    check;
    exit;
end;
a[i]:=0;
find(i+1);
if (i=1)or(a[i-1]=0) then begin
    a[i]:=1;
    find(i+1);
end;
end;

begin
read(n);
ans:=0;
find(1);
writeln(ans);
end.

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

var ans:integer;
    a:array[1..100] of integer;
    n:integer;

function check:integer;
begin
result:=1;
end;

function find(i:integer):integer;
begin
if i>n then begin
    result:=check;
    exit;
end;
a[i]:=0;
result:=find(i+1);
if (i=1)or(a[i-1]=0) then begin
    a[i]:=1;
    result:=result+find(i+1);
end;
end;

begin
read(n);
ans:=find(1);
writeln(ans);
end.

Т.е. помните мотивировку рекурсивного перебора? "Функция find предполагает, что мы уже заполнили первые $i-1$ элементов массива и перебирает варианты заполнения оставшихся." Так вот, в модифицированном варианте функция будет еще и возвращать количество способов заполнить оставшиеся. Осознайте, почему это работает.

А теперь самое главное. Зададимся вопросом: от чего на самом деле зависит результат работы функции find? Пусть, например, мы рассматриваем запуск find(15). Это обозначает, что мы заполнили первые 14 элементов массива. Так вот: зависит ли возвращаемое значение функции find(15) от всех значений всех этих элементов?

Достаточно очевидно, что нет. Более того, если подумать, то понятно, что возвращаемое значение зависит только от собственно i, а также от значения a[i-1]. Значения предыдущих элементов массива нам не важны. Например, результат вызова find(5) будет один и тот же, если массив a перед вызовом равен 1 0 1 1 или 0 1 1 1, но для массива 1 0 1 0 результат будет другой.

Это позволяет резко ускорить решение, причем двумя способами. Первый способ состоит в том, чтобы распознавать ситуации, эквивалентные тем, которые мы уже решали раньше — и не перерешивать заново. А именно, пусть мы запускаем find(i), и при этом a[i-1]=x. Запишем результат этой процедуры в специальный массив res в элемент res[i,x]. После этого когда окажется, что мы опять запускаем find(i) с тем же самым i и тем же самым a[i-1], то мы не будем все рассчитывать заново, а просто сразу вернем значение, уже записанное в res[i,x]. Примерно так:

var res:array[1..100,0..1] of integer;
    ...

function find(i:integer):integer;
begin
if i>n then begin
    result:=check;
    exit;
end;
if res[i,a[i-1]]=-1 then begin // если мы еще не решали эту задачу
    a[i]:=0;
    res[i,a[i-1]]:=find(i+1);
    if (i=1)or(a[i-1]=0) then begin
        a[i]:=1;
        res[i,a[i-1]]:=res[i,a[i-1]]+find(i+1);
    end;
end;
result:=res[i,a[i-1]];
end;

Это еще не совсем рабочий код, в нем надо как минимум аккуратно разобраться со случаем i=1, а еще можно и функцию check исключить, но, я думаю, идея понятна. Собственно, это то, что называется рекурсией с запоминанием результата, и это уже полноценное ДП.

Но чтобы более четко понять, что происходит, и написать уже совсем классическое ДП, пойдем немного другим способом. А именно, заметив, что ответ зависит только от i и a[i-1], попробуем сразу это и сделать подзадачами ДП. А именно, давайте для каждого i и x вычислим res[i,x] как значение, которое вернет наша функция find(i), запущенная в ситуации, когда a[i-1]=x. Результат функции зависит только от i и x, поэтому наш вопрос корректен.

Как мы будем вычислять res[i,x]? У нас уже есть функция find, и она фактически документирует способ этого вычисления. Во-первых, если i>n, то ответ будет 1. Иначе функция find рекурсивно запускает себя один или два раза в зависимости от a[i-1] (т.е. x). Несложно прямо из когда нашей функции видеть, что выполняется следующее соотношение:

res[i,x]=res[i+1,0]             если x=1
res[i,x]=res[i+1,0]+res[i+1,1]  если x=0

Вот и готова динамика! Несложно также видеть, что нам надо идти по убыванию i, т.к. каждая подзадача зависит от подзадач с бОльшим i, и теперь решение пишется легко:

res[n+1,0]:=1;
res[n+1,1]:=1; // это особые случаи, отвечающие функции check
for i:=n downto 1 do begin
    res[i,1]:=res[i+1,0];
    res[i,0]:=res[i+1,0]+res[i+1,1];
end;
writeln(res[1,0]); // поймите, почему именно так?

Вот и все. Мы придумали подзадачи и получили рекуррентное соотношение, просто задавшись одним вопросом: от чего на самом деле зависит результат функции find?

Конечно, его можно улучшить: можно первую формулу подставить во вторую:

res[i,0]=res[i+1,0]+res[i+2,0]

И теперь мы видим, что элементы с x=1 нам больше не нужны, и переобозначая res[i,0] как просто res[i], получаем уже привычное рекуррентное соотношение для этой задачи. Правда, пожалуй, рекуррентные соотношения с двумя элементами массива, в общем-то, представляются даже более естественными для этой задачи.

Оно (да и рекуррентные соотношения выше), правда, записано "задом-наперед", но это не так страшно. Если подумать, то все понятно: в обычной динамике мы задавались вопросом "как можно заполнить первые i позиций" (т.е. сколько есть решений длины i), а тут мы задаемся вопросов "как можно заполнить последние n-i позиций" (так и работал перебор). Поэтому и цикл от n вниз, и рекуррентное соотношение ссылается на бОльшие i. Но это уже детали.

Общая идея

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

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

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

Пример: набор заданной суммы данным набором монет

Нам надо набрать некоторую сумму S, используя монеты достоинством a[1], a[2], ..., a[n]. Каждую монету можно использовать не более одного раза.

Давайте придумаем переборное решение. Помня, что динамика из перебора получается "задом-наперед", я сразу придумаю перебор "задом-наперед", чтобы динамика получилась нормальной. А именно, я буду запускать из главной программы find(n), она будет решать, берем ли мы n-ую монету и запускать find(n-1) и т.д.:

function check:boolean;
var cursum:integer;
    i:integer;
begin
for i:=1 to n do
    if taken[i]=1 then
        cursum:=cursum+a[i];
result:=cursum=s;
end;

function find(i:integer):boolean;
begin
if i=0 then begin
    result:=check;
    exit;
end;
taken[i]:=0;
result:=find(i-1);
taken[i]:=1;
result:=result or find(i-1);
end;

begin
...
fillchar(taken,sizeof(taken),0);
res:=find(n);
writeln(res);
end.

Я даже тут не стал делать никаких отсечений. Я просто перебираю все варианты "брать-не брать" и потом проверяю, получилась ли нужная сумма.

Давайте подумаем, от чего зависит результат функции find. Если немного подумать, то несложно понять, что нам действительно не надо знать, какие конкретно числа мы поставили в массив taken, т.е. какие конкретно монеты мы решили брать. Нам надо лишь знать общую сумму, которую мы уже набрали этими монетами. Ну и i, конечно, тоже надо знать.

Обозначая уже набранную сумму как x, получаем сразу рекуррентное соотношение для динамики:

Собственно, это и есть стандартное рекуррентное соотношение для этой задачи; только обычно вместо x используют S-x — сумму, которую осталось набрать, но это несущественно. Кроме того, можно только еще догадаться, что решать подзадачи с x>S не надо — и добавить соответствующий if, но это уже технические детали, которые несложно добавить (да и не всегда необходимо).

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