Dynamic programming in olympiad problems

Hello!

Recently I solved problems from the Timus Online Judge archive and came across a section called dynamic programming tasks . Tasks of this type make me particularly interested, because often this approach ensures the speed and elegance of the solution. What is dynamic programming?

Dynamic programming is an approach to problem solving, in which there is a division into subtasks that are “simpler” in comparison with the original one. The word "dynamic" is close in meaning to "inductive": it is assumed that the answer is known for some value $$$k$and I want to find the answer for $$$k + 1$. In mathematics, this is called an inductive transition, and constitutes the basic idea of ​​dynamic programming.
')

Simple examples

The most striking and illustrative task is the task of computing $$$n$th Fibonacci sequence number. It is known that the sequence has the following properties:

$$

$$F_0 = F_1 = 1, \ F_n = F_ {n-1} + F_ {n-2}.$$

This immediately implies the recurrence formula:

int Fibonacci(int n) { if(n == 1 || n == 2) return 1; return Fibonacci(n-1) + Fibonacci(n-2); } 

If the recursion searches for the number “from the end”, then the following method sequentially calculates all the numbers between $$$0$and $$$n$:

 int dpFibonacci(int n) { int prev1 = 1; int prev2 = 1; int curr = 0; for(int j = 2; j < n; j++) { curr = prev1 + prev2; prev1 = prev2; prev2 = curr; } return curr; } 

It is clear that with sufficiently large $$$n$This algorithm is much faster: it does not calculate intermediate values ​​several times. Consider a slightly more complex example.

Example 1. You walk up the toll ladder. To step on $$$i$step you need to pay $$$a_i$of coins. You can step to the next step or jump over one. Task: to pass $$$n$steps and spend as little coins as possible.

It is clear that stepping over each step, we minimize the number of "payments", but we can run into a very expensive step that we would like to avoid. Create an array of values $$$d$in which on $$$j$The first place will be the (minimum) number of coins that must be spent to get to $$$j$th steps. It is immediately clear that $$$d_1 = a_1, \ d_2 = a_2$. And then we will take at least two previous steps and add the cost of the step itself:

$$

$$d_i = \ min \ left (d_ {i-1}, d_ {i-2} \ right) + a_ {i}.$$

We change the conditions of the problem a little: suppose that at some steps you can receive coins (this will mean that $$$a_k <0$). What needs to be changed in the algorithm so that it gives the correct result?


Consider another example that uses the "two-dimensional" dynamics.

Example 2. The maze has $$$n \ times m$rooms, each of which is gold (in a cage $$$(i, j)$lies $$$a_ {ij}$gold). The task is to determine what the maximum amount of gold can be collected with the optimal route from the point $$$(0,0)$exactly $$$(n, m)$if you can go either down or to the right.

So, we want to know the optimal route to the cell. $$$(i, j)$. Here we can get from two cells - $$$(i-1, j)$and $$$(i, j-1)$. Given that the optimal routes for these two cells are known (they are stored in a table $$$d$), then the answer is for the cell $$$(i, j)$is obtained as follows:

$$

$$d_ {ij} = \ max \ left (d_ {i-1j}, d_ {ij-1} \ right) + a_ {ij}.$$

This is another classic dynamic programming problem, modifications of which are quite often encountered in problems of sports programming. More similar problem is explained here .

More challenging tasks

If desired, the dynamic approach can be screwed anywhere. Consider a task from the Timus Online Judge archive.

The mathematical formulation of the problem is as follows: it is required to find the minimum number of terms required to decompose a given number into full squares.

As before, suppose we know the answers for all numbers. $$$k-1$that are stored in an array $$$d$and we would like to find $$$d_ {k}$.

Take this number $$$k$and analyze what could be the situation:

1. $$$k$is a complete square. In this case $$$d_ {k} = 1$.
2. Perhaps the previous number $$$k-1$was a complete square. Then $$$d_ {k} = d_ {k-1} + 1$.

In general, the option of adding one to the previous one does not seem so bad.

We proceed as follows: we will seek expansion $$$k = q ^ 2 + s$such that

$$

$$d_ {q ^ 2} + d_s <d_ {k-1} + 1.$$

Because $$$q ^ 2$- full square, then $$$d_ {q ^ 2} = 1$and

$$

$$d_s <d_ {k-1},$$

that is, we found a partition that is simply better than $$$d_ {k-1} + 1$and the answer in this case will be

$$

$$d_k = d_ {s} + d_ {q ^ 2} = d_s + 1.$$

Consider the following problem . The goal is to build a ladder from $$$N$cubes by the rules:

1. the staircase has at least two steps;
2. a staircase cannot have two identical steps;
3. steps of a ladder go in ascending order (that is, the next one is greater than the previous one).

This time we will build a two-dimensional dynamics. Create a tab $$$d$in which position $$$(i, j)$will lie the number of stairs consisting of $$$i$cubes whose height does not exceed $$$j$. If it works, then the answer to our problem will be the amount

$$

$$\ sum \ limits_ {j = 1} ^ n d_ {nj}.$$

So, we will solve the problem of finding the number of stairs composed of $$$i$cubes that have height $$$j$. The picture shows the stairs that fall into $$$d_ {74}$:

Since we know all the stairs, which consist of a smaller number of cubes, we “split” from the stairs $$$(i, j)$right column. The result is a staircase c $$$i-j$cubes. Example for $$$i = 9, \ j = 4$:

But for such stairs, the result is already known, so we will sort through all such stairs in a cycle $$$k$and add up all the results. In this way,

$$

$$d_ {ij} = \ sum \ limits_ {k = 1} ^ {j-1} d_ {i-jk}.$$

Now we will go through the height of the stairs:

$$

$$d_ {ij} = \ sum \ limits_ {k = 1} ^ {j-1} d_ {i-jk}, \ j = \ overline {1, i}.$$

Finally, changing $$$i$from $$$1$before $$$n$will get the answer.

Important : in the process of building our matrix, you need to consider $$$d_ {ii} = 1$, because otherwise, some types of ladders will be “lost” (during “splitting off”), but it goes without saying that such a ladder does not satisfy the conditions of the task, therefore the answer will be the number $$$d_ {nn} - 1$.


The next problem is solved using a one-dimensional array.

So what we have. The first ent knows 2 words. Each ent teaches all the words that he knows himself, two ents: young and old. In turn, the young were taught as many more words as he already knows, and the old were taught only one word. Need to know how many ents know exactly $$$K$words (you must print the number of these ents modulo $$$P$).

The solution is quite simple. Create an array $$$d$in which on $$$i$th place we will store the number of ents (modulo $$$P$who know $$$i$of words. It all starts with the first ent who knows two words, so $$$d_2 = 1$. And then everything is simple:

• All ents who know an odd number of words are old and could only learn from previous ones. Therefore for odd $$$i: \ d_i = d_ {i-1};$
• As for the Ents, who know an even number of words - these are all those who received the same number of words from the elves (young) $$$+$those who have learned from previous ones (old ones); that is, for even $$$i$we have $$$d_i = d _ {{i \ backslash 2}} + d_ {i-1}$.

It remains to understand the calculation of the module. In order not to store huge numbers, we will immediately memorize all the values ​​in the module.


Resources used:

1. Timus Online Judge;
2. A little bit about dynamic programming;
3. Comparison properties modulo.