PrevNext
Very Frequent
 0/16

Introduction to DP

Authors: Michael Cao, Benjamin Qi, Neo Wang, Daniel Zhu

Speeding up naive recursive solutions with memoization.

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

Resources
CPH

Great introduction that covers most classical problems. Mentions memoization.

TC

General tutorial, great for all skill levels

CPC

Contains examples with nonclassical problems

CP2

Describes many ways to solve the example problem + additional classical examples

HR

Covers classical problems

AR

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

Resources
YouTube

Great introduction video

YouTube

Errichto DP video regarding coin change

YouTube

Errichto DP problem editorial

YouTube

Animated DP videos that pertain to interview questions

Pro Tip

It's usually a good idea to write a slower solution first. For example, if the complexity required for full points is O(N)\mathcal{O}(N) and you come up with a simple O(N2)\mathcal{O}(N^2) solution, then you should definitely type that up first and earn some partial credit. Afterwards, you can rewrite parts of your slow solution until it is of the desired complexity. The slow solution might also serve as something to stress test against.

Example - Frog 1

Focus Problem – try your best to solve this problem before continuing!

The problem asks us to compute the minimum total cost it takes for a frog to travel from stone 11 to stone N(N105)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 ii and jj is given by hihj|h_i - h_j|, where hih_i represents the height of stone ii.

Without Dynamic Programming

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

Since there are only two options, we can use recursion to compute what would happen if we jumped either 11 stone, or 22 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,11,2,1 and 2,1,22,1,2 reuses the state of stone 33. Dynamic programming provides the mechanism to cache such states.

With Dynamic Programming

Time Complexity: O(N)\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 dp[i]\texttt{dp}[i] as the minimum cost to reach stone ii. Then, our transitions are as follows:

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

    dp[i+1]=min(dp[i+1],dp[i]+heightiheighti+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 heightiheighti+2|\text{height}_i - \text{height}_{i + 2}|:

    dp[i+2]=min(dp[i+2],dp[i]+heightiheighti+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 dp[0]=0\texttt{dp}[0] = 0, since the frog is already on that square, and proceed to calculate dp[1],dp[2],dp[N1]\texttt{dp}[1], \texttt{dp}[2], \ldots \texttt{dp}[N - 1].

C++

#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

Java

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(); }

Python

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 ii: from stone i1i - 1 and stone i2i - 2.

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

    dp[i]=min(dp[i],dp[i1]+heightiheighti1)\texttt{dp}[i] = \min(\texttt{dp}[i], \texttt{dp}[i - 1] + |\text{height}_i - \text{height}_{i - 1}|)
  • Jump from stone i2i - 2, incurring a cost of heightiheighti2|\text{height}_i - \text{height}_{i - 2}|:

    dp[i]=min(dp[i],dp[i2]+heightiheighti2)\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 dp[0]=0\texttt{dp}[0] = 0, since the frog is already on that square, and proceed to calculate dp[1],dp[2],dp[N1]\texttt{dp}[1], \texttt{dp}[2], \ldots \texttt{dp}[N - 1].

C++

#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

Java

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(); }

Python

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

Resources
CSES

You should know how to do all of these once you're finished with the DP section. Editorials are available here.

AC

Some tasks are beyond the scope of Gold. Editorials are available here.

CF

Beginner-friendly classical problems. Some tasks requires input/output files. The solutions can be found here

CF

Good practice problems. You should be able to do most of these after completing the Gold DP module. Some problems might be out of the scope for gold.

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.

Note - Ordering of DP Modules

You are not expected to complete all of the problems below before starting the other DP modules. In particular, we recommend that you begin with the "easy" problems from the knapsack module if this is your first encounter with DP.

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsDP
CFEasy
Show TagsDP
GoldEasy
Show TagsDP
GoldEasy
Show TagsDP
GoldNormal
Show TagsDP
GoldNormal
Show TagsDP
IOINormal
Show TagsDP
CFHard
Show TagsBFS, DP

Harder USACO

StatusSourceProblem NameDifficultyTags
GoldHard
Show TagsDP
GoldHard
Show TagsDP
GoldHard
Show TagsDP, Prefix Sums
GoldHard
Show TagsAPSP, DP, Prefix Sums
PlatinumHard
Show TagsDP
GoldVery Hard
Show TagsDP
GoldVery Hard
Show TagsDP

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext