Module 1: Scanline

Scanline / Event Processing

Module 2: Introduction to DP

Introduction to Dynamic Programming

Module 3: Number theory

Prime numbers and factorization
Sieve of Eratosthenes

Module 4: Graph traversals

Depth-First Search (DFS)
Breadth-First Search (BFS)
Bipartiteness check
Finding connected components
Topological sorting

Module 5: Shortest paths

Dijkstra's algorithm
Floyd–Warshall Algorithm
Bellman–Ford algorithm

Module 6: Game Theory - Basics

Basics of Game States

Module 7: Introduction to Geometry

Signed area of a triangle
Basic Geometry
Bonus Geometry Problems

Module 8: Various types of Binary Search

Binary search by answer
Binary search on a real-valued answer
Ternary search
Binary search by powers of two

Introduction to Dynamic Programming - Preparation to IOI Part 2

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Preparation to IOI Part 2/Module 2: Introduction to DP/Introduction to Dynamic Programming

Introduction to Dynamic Programming

Learn basic concepts of dynamic programming

Basic Dynamic Programming

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.

1 \leq j \leq 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]);
}