Dinamik dasturlash - Resources

Bosh sahifa Kurslar Resurslar Masalalar Milliy olimpiada Musobaqalar Reyting

...

Bosh sahifa/Resources/Dynamic Programming/Dinamik dasturlash

Dinamik dasturlash

Introduction

Dynamic programming is a way to solve complex problems by breaking them down into simpler subproblems.

The Turtle Problem

A table of $N$ rows and $M$ columns is given. In each cell $(i, j)$ , where $1 \le i \le N$ , $1 \le j \le M$ , there are coins.

External Problems

Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

ATCODERA. Frog 1

ATCODERB. Frog 2

ATCODERC. Vacation

ATCODERB. Ancestor

ATCODERB. Lucas Number

ATCODERC. chokudai

ATCODERC. Jumping Takahashi

ATCODERD. Bonus EXP

CODEFORCESLong Jumps

CODEFORCESVitamins

CODEFORCESKousuke's Assignment

CODEFORCESCards

CODEFORCESCut Ribbon

CODEFORCESVacations

CODEFORCESMike and Fun

CODEFORCESSakurako's Field Trip

CODEFORCESBoredom

CODEFORCESNikita and string

CODEFORCESMortal Kombat Tower

CODEFORCESPalindrome Basis

CODEFORCESBoredom

CODEFORCESArt Union

1≤

j≤

M

C_{i, j}

In the upper left corner there is a turtle, that is, in the cell $(1, 1)$ . The turtle can move only down or to the right. The turtle needs to reach the cell $(N, M)$ , collecting the maximum number of coins.

How do we solve this problem? Let’s first try to solve it using recursion.

Let $Rec(x, y)$ denote the maximum number of coins that the turtle can collect if it starts from $(1, 1)$ and reaches the cell $(x, y)$ . Then the answer will be $Rec(N, M)$ .

Base case: $x = 1$ and $y = 1$ , that is, the turtle does not need to go anywhere.
Otherwise, let’s see where the turtle could have come to the cell $(x, y)$ from: either from above $(x-1, y)$ , or from the left $(x, y-1)$ . Then

Rec(x, y) = \max(Rec(x-1, y),\ Rec(x, y-1)) + C_{x, y}

Now let’s return to dynamic programming. The principle of DP is very similar to the principle of recursion.
Let’s recall what DP is: dynamic programming is a way to solve a problem by breaking it down into simpler subproblems.

That is exactly what we did above. To find the answer $Rec(x, y)$ (for $x > 1$ or $y > 1$ ) we computed the values of simpler problems — $Rec(x-1, y)$ and $Rec(x, y-1)$ .

In this case:

DP state is $(x, y)$ , that is, which cell the turtle must reach (a subproblem).
Transition is a way to compute $Rec(x, y)$ through other states.

Usually, when solving dynamic programming problems, the following logic is followed:

Come up with DP states, that is, understand how to break the problem into smaller subproblems.
Determine base states — just like in recursion, you need to understand for which states the answer is known in advance.
After that, come up with transitions, that is, how for each state to compute the answer using simpler subproblems.

A question arises: what, then, is the difference between dynamic programming and recursive brute force?
In both cases we have states and transitions between them.

The difference is that in dynamic programming the same states are not computed multiple times, whereas in ordinary recursion they can be computed repeatedly.

Let’s recall the lesson on recursion with memorization (memoization), where we discussed why recursion can recompute the same values and how to solve this problem.

The same idea can be applied here as well. If we add memorization to the recursive solution, then we will effectively get a solution using dynamic programming.

The Turtle and an Array

The turtle found an array $a$ of $n$ numbers. The turtle needs to choose some subset of these numbers so that their sum is maximal among all possible options.
However, there is a restriction: you cannot choose two adjacent numbers at the same time.

How do we solve this problem?

Let’s find the DP states. Let $dp(i)$ be the maximum sum that the turtle can collect using only the elements of the prefix of length $i$ .
That is, we consider the array $[a_1, a_2, \ldots, a_i]$ .
Base cases:
- $dp(0) = 0$ — there is nothing to take on an empty prefix.
- $dp(1) = a_1$ — the only number on the prefix.
Now consider how to compute $dp(i)$ for $i > 1$ . Two options are possible:
1. The turtle takes the number at position $i$ .
  Then it cannot take $a_{i-1}$ , so it can use only the prefix
  . The sum in this case is .

As a result, we obtain the DP formula:

dp(0) = 0,\quad dp(1) = a_1

dp(i) = \max\big(dp(i-2) + a_i,\ dp(i-1)\big), \quad 2 \le i \le n

The answer to the original problem will be the value $dp(n)$ .

[a_1, a_2, \ldots, a_{i-2}]

[a_{1}, a_{2}, \dots, a_{i - 2}]

dp(i-2) + a_i

The turtle does not take the number at position $i$ .
Then it can use the prefix
$[a_1, a_2, \ldots, a_{i-1}]$ , and the sum is $dp(i-1)$ .

int Rec(int x, int y) {
    if (x == 1 && y == 1) {
        return C[1][1];
    } else {
        int best = 0;
        if (x > 1) {
            best = max(best, Rec(x - 1, y));
        }
        if (y > 1) {
            best = max(best, Rec(x, y - 1));
        }
        return best + C[x][y];
    }
}

map<pair<int, int>, int> mem;
int Rec(int x, int y) {
    if (x == 1 && y == 1) {
        return C[1][1];
    } else {
        if (mem.find({x, y}) != mem.end()) {
            return mem[{x, y}];
        }
        int best = 0;
        if (x > 1) {
            best = max(best, Rec(x - 1, y));
        }
        if (y > 1) {
            best = max(best, Rec(x, y - 1));
        }
        return mem[{x, y}] = best + C[x][y];
    }
}

dp[0] = 0;
dp[1] = a[1];
for (int i = 2; i <= n; i++) {
    dp[i] = max(dp[i - 2] + a[i], dp[i - 1]);
}