Introduction to DP

Dynamic Programming (DP) is an important algorithmic technique in Competitive Programming from the gold division to competitions like the International Olympiad of Informatics. By breaking down the full task into sub-problems, DP avoids the redundant computations of brute force solutions.

Although it is not too difficult to grasp the general ideas behind DP, the technique can be used in a diverse range of problems and is a must-know idea for competitors in the USACO Gold division.

General Resources

If you prefer watching videos instead, here are some options:

Example - Frog 1

The problem asks us to compute the minimum total cost it takes for a frog to travel from stone $1$ to stone $N (N \le 10^5)$ given that the frog can only jump a distance of one or two. The cost to travel between any two stones $i$ and $j$ is given by $|h_i - h_j|$, where $h_i$ represents the height of stone $i$.

Without Dynamic Programming

Time Complexity: $\mathcal{O}(2^N)$

Since there are only two options, we can use recursion to compute what would happen if we jumped either $1$ stone, or $2$ stones. There are two possibilities, so recursively computing would require computing both a left and right subtree. Therefore, for every additional jump, each branch splits into two, which results in an exponential time complexity.

However, this can be sped up with dynamic programming by keeping track of "optimal states" in order to avoid calculating states multiple times. For example, recursively calculating jumps of length $1,2,1$ and $2,1,2$ reuses the state of stone $3$. Dynamic programming provides the mechanism to cache such states.

With Dynamic Programming

Time Complexity: $\mathcal{O}(N)$

There are two main DP approaches:

• Push DP, where we update future states based on the current state
• Pull DP, where we calculate the current state based on past states

We present both approaches below.

Push DP

There are only two options: jumping once, or jumping twice. Define $\texttt{dp}[i]$ as the minimum cost to reach stone $i$. Then, our transitions are as follows:

• Jump one stone, incurring a cost of $|\text{height}_i - \text{height}_{i+1}|$:

  $$\texttt{dp}[i + 1] = \min(\texttt{dp}[i + 1], \texttt{dp}[i] + |\text{height}_i - \text{height}_{i + 1}|)$$

• Jump two stones, incurring a cost of $|\text{height}_i - \text{height}_{i + 2}|$:

  $$\texttt{dp}[i + 2] = \min(\texttt{dp}[i + 2], \texttt{dp}[i] + |\text{height}_i - \text{height}_{i + 2}|)$$

We can start with the base case that $\texttt{dp}[0] = 0$, since the frog is already on that square, and proceed to calculate $\texttt{dp}[1], \texttt{dp}[2], \ldots \texttt{dp}[N - 1]$.

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> height(N);
	for (int i = 0; i < N; i++) { cin >> height[i]; }

	// dp[N] is the minimum cost to get to the Nth stone

Copy
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int N = io.nextInt();
		int[] height = new int[N];
		for (int i = 0; i < N; ++i) { height[i] = io.nextInt(); }

Copy
stone_num = int(input())
# height is 1-indexed so it can match up with dp
height = [0] + [int(s) for s in input().split()]
assert stone_num == len(height) - 1

"""
dp[N] is the minimum cost to get to the Nth stone
(we initially set all values to INF)
"""
dp = [float("inf") for _ in range(stone_num + 1)]

Pull DP

There are two ways to get to stone $i$: from stone $i - 1$ and stone $i - 2$.

• Jump from stone $i - 1$, incurring a cost of $|\text{height}_i - \text{height}_{i-1}|$:

  $$\texttt{dp}[i] = \min(\texttt{dp}[i], \texttt{dp}[i - 1] + |\text{height}_i - \text{height}_{i - 1}|)$$

• Jump from stone $i - 2$, incurring a cost of $|\text{height}_i - \text{height}_{i - 2}|$:

  $$\texttt{dp}[i] = \min(\texttt{dp}[i], \texttt{dp}[i - 2] + |\text{height}_i - \text{height}_{i - 2}|)$$

We can start with the base case that $\texttt{dp}[0] = 0$, since the frog is already on that square, and proceed to calculate $\texttt{dp}[1], \texttt{dp}[2], \ldots \texttt{dp}[N - 1]$.

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> height(N);
	for (int i = 0; i < N; i++) { cin >> height[i]; }

	// dp[N] is the minimum cost to get to the Nth stone

Copy
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int N = io.nextInt();
		int[] height = new int[N];
		for (int i = 0; i < N; ++i) { height[i] = io.nextInt(); }

Copy
N = int(input())
height = [int(s) for s in input().split()]

"""
dp[N] is the minimum cost to get to the Nth stone
(we initially set all values to INF)
"""
dp = [float("inf") for _ in range(N)]
# dp[0] = 0 is our base case since we're already at the first stone
dp[0] = 0

Classical Problems

The next few modules provide examples of some classical problems: Dynamic Programming problems which are well known. However, classical doesn't necessarily mean common. Since so many competitors know about these problems, problemsetters rarely set direct applications of them.

Problemsets

Some of these problems will be mentioned in the next few modules.

Introductory Problems

Easier problems that don't require many optimizations or complex states.

Harder USACO