About the connection of recursive backtracking and DP, or How to turn recursive backtrack solutions into DP

(Over time, I will add this text to the main text about DP. This material is optional at level 2. If you haven't mastered recursive backtrack, then skip this material as well. If you have mastered recursive backtrack, then read this text and try to understand it, although in fact the ideas outlined below are not necessary to solve level 2 problems, at level 2 in DP the tasks are quite simple.)

Example: sequences of zeros and ones

Let's say you have come up with a backtrack solution to some problem. It often happens that it is not difficult to turn it into a solution by dynamic programming. For example, consider our favorite problem about sequences of zeros and ones without two neighbour ones. Assume we did not thought about the DP solution. Let's write a backtrack solution with adequate cut-offs:

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.

This implementation has a drawback that will hinder us now — this is the global variable ans. Let's rewrite the code so that it doesn't use a global variable: let's make all procedures functions that return how many sequences they found:

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.

That is, do you remember the motivation of recursive iteration? "The find function assumes that we have already filled in the first $i-1$ elements of the array and iterates over the options for filling in the remaining ones." So, in the modified version, the function will also return the number of ways to fill in the remaining ones. Understand why it works.

And now the most important thing. Let's ask ourselves the question: what does the result of the find function really depend on? Let's say, for example, we are considering running find(15). This means that we have filled in the first 14 elements of the array. So: does the return value of find(15) depend on all the values of all these elements?

It's pretty obvious that it does not. Moreover, if you think about it, it is clear that the return value depends only on the actual i, as well as on the value of a[i-1]. The values of the previous array elements are not important to us. For example, the result of calling find(5) will be the same if the array a before the call is 1 0 1 1 or 0 1 1 1, but for array 1 0 1 0 the result will be different.

This allows you to dramatically speed up the solution, and in two ways. The first way is to recognize situations that are equivalent to those that we have already solved before — and not to re-solve. Namely, let's consider running find(i), given a[i-1]=x. Let's write the result of this procedure in a special array res to the element res[i,x]. After that, when it turns out that we are running find(i) again with the same i and the same a[i-1], then we will not calculate everything again, but simply immediately return the value already written in res[i,x]. Something like this:

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 // if we haven't solved this subproblem yet
    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;

This is not quite working code yet, it needs at least to carefully deal with the case of i=1, and you can also exclude the check function, but I think the idea is clear. Actually, this is what is called recursion with memorization of the result, and this is already a full-fledged DP.

But in order to understand more clearly what is happening and write a completely classic DP, let's go a little differently. Namely, having noticed that the answer depends only on i and a[i-1], let's try to do it right away and do it with DP subtasks. Namely, for each i and x let's calculate the value res[i,x] as the value that our find(i) function returns, launched in the situation when a[i-1]=x. The result of the function depends only on i and x, so our question is correct.

How will we calculate res[i,x]? We already have the find function, and it actually documents the way this calculation is done. First, if i>n, then the answer will be 1. Otherwise, the find function recursively runs itself once or twice depending on a[i-1] (i.e. x). It is not difficult to see right from the beginning of our function that the following relation holds:

res[i,x]=res[i+1,0]             if x=1
res[i,x]=res[i+1,0]+res[i+1,1]  if x=0

Now the dynamics are ready! It is also easy to see that we need to go in descending order i, because each subtask depends on subtasks with a large i, and now the solution is written easily:

res[n+1,0]:=1;
res[n+1,1]:=1; // these are special cases that correspond to the check function
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]); // do understand why this is so

That's it. We came up with subtasks and got a recurrence relation, just asking one question: what does the result of the find function really depend on?

Of course, it can be improved: you can substitute the first formula into the second:

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

And now we see that we no longer need elements with x=1, and reinterpreting res[i,0] as just res[i], we get the already familiar recurrence relation for this task. Admittedly, perhaps, the recurrent relation with two elements of the array seems more natural for this task.

All the formulas above, however, are written "backwards", with subtask i depending on subtask i+1, but it's not so scary. If you think about it, then everything is clear: in normal dynamics, we were wondering "how can I fill the first i positions" (i.e. how many solutions of length i are there), and here we are asking questions "how can I fill the last n-i positions" (this is how the backtrack worked). Therefore, both the loop runs from n downwards, and the recurrence relation refers to larger is. But these are details, and it is not a big deal to rethink the formulas to make them work with ascending is.

General idea

So, the general idea. Let's say you have come up with a backtrack solution to some problem. Re-think it so that your find function returns the result, and does not work with any global variables. Think about what the result returned by your function depends on. Often it will depend not on the whole set of choices that you have made before, but on some characteristic of this set. Great, now all the possible values of this characteristic (or several characteristics) will become subtasks in your dynamics; and how your backtrack function works will become a recurrence relation.

You don't even have to directly write backtrack code; you can just imagine it in your mind.

Of course, this approach will not always work. Often the problem can be solved by backtracking in different ways, and only some of them will lead to a good dynamic solution. But nevertheless, the approach, it seems to me, is very useful.

Example: a change of a given amount by a given set of coins

We need to collect some amount of S using coins of the denominations a[1], a[2], ..., a[n]. Each coin can be used no more than once.

Let's come up with an backtrack solution. Remembering that the dynamics from backtracking turns out running "backwards", I will immediately come up with a backtrack solution that itself runs "backwards" so that the dynamics will turn out to be normal. Namely, I will run find(n) from the main program, it will decide whether we take the nth coin and run find(n-1), etc.:

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.

I didn't even make any cuts here. I'm just going through all the options "to take or not to take" and then check if the right amount has turned out.

Let's think about what the result of the find function depends on. If you think a little, it's easy to understand that we really don't need to know which specific numbers we put in the taken array, i.e. which specific coins we decided to take. We just need to know the total amount that we have already collected with these coins. Well, and, of course, we need to know i.

Denoting the amount already taken as x, we immediately get a recurrence relation for dynamics:

Actually, this is the standard recurrence relation for this task; only usually, instead of x, S-x is used — the amount that remains to take, but this is insignificant. In addition, one can understand that it is not necessary to solve subtasks with x>S — and add the corresponding if, but these are technical details that are easy to add (and not always necessary).

So pay attention once again to how easily we came up with these subtasks. If you have not thought about backtrack, then it may seem very unobvious that the dynamics parameter should be the amount to be typed (or which you have already typed) — but if you have already thought about the backtrack solution and wondered "what determines the result of the find call" — then it becomes almost obvious.