Introducción a la DP

La programación dinámica (DP) es una técnica algorítmica importante en programación competitiva, desde la división Oro hasta competencias como la Olimpiada Internacional de Informática. Al partir la tarea completa en subproblemas, la DP evita los cálculos redundantes de las soluciones de fuerza bruta.

Aunque no es demasiado difícil captar las ideas generales de la DP, la técnica se puede usar en una gama muy amplia de problemas y es una idea imprescindible para los competidores de la división Oro de USACO.

Recursos generales

Recursos
Fuente	Recurso	Notas
CPH	7 - DP	Excelente introducción que cubre la mayoría de los problemas clásicos. Menciona memoización.
TC	DP from Novice to Advanced	Tutorial general, útil para todos los niveles
CPC	6 - DP	Incluye ejemplos con problemas no clásicos
CP2	3.5 - DP	Describe varias formas de resolver el problema de ejemplo + más ejemplos clásicos
HR	DP	Cubre problemas clásicos
AR	Dynamic Programming for Computing Contests

Si se prefiere ver videos, estas son algunas opciones:

Recursos
Fuente	Recurso	Notas
YouTube	Errichto DP #1 - Fibonacci, iteration vs recursion	Muy buen video de introducción
YouTube	Errichto DP #2 - Coin change, double counting	Video de Errichto sobre DP y el problema de las monedas
YouTube	Errichto DP #3 - Line of Wines	Editorial de un problema de DP de Errichto
YouTube	WilliamFiset DP Videos	Videos animados de DP orientados a preguntas de entrevista

Ejemplo - Frog 1

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	AC	Frog 1	Fácil	DP	en el módulo

El problema pide calcular el costo total mínimo para que una rana viaje de la piedra $1$ a la piedra $N (N \le 10^5)$ sabiendo que solo puede saltar una distancia de uno o de dos. El costo de viajar entre dos piedras cualesquiera $i$ y $j$ es $|h_i - h_j|$ , donde $h_i$ es la altura de la piedra $i$ .

Sin programación dinámica

Complejidad temporal: $\mathcal{O}(2^N)$

Como solo hay dos opciones, podemos usar recursión para calcular qué pasaría si saltamos $1$ piedra o $2$ piedras. Hay dos posibilidades, así que el cálculo recursivo exige calcular tanto un subárbol izquierdo como uno derecho. Por lo tanto, con cada salto adicional cada rama se parte en dos, y la complejidad temporal resulta exponencial.

Sin embargo, esto se puede acelerar con programación dinámica guardando “estados óptimos” para no calcular estados varias veces. Por ejemplo, calcular de forma recursiva saltos de longitud $1,2,1$ y $2,1,2$ reutiliza el estado de la piedra $3$ . La programación dinámica da el mecanismo para cachear esos estados.

Con programación dinámica

Complejidad temporal: $\mathcal{O}(N)$

Hay dos enfoques principales de DP:

Push DP, donde actualizamos estados futuros a partir del estado actual
Pull DP, donde calculamos el estado actual a partir de estados pasados

Presentamos ambos enfoques a continuación.

Push DP

Solo hay dos opciones: saltar una vez o saltar dos veces. Definimos $\texttt{dp}[i]$ como el costo mínimo para llegar a la piedra $i$ . Entonces, las transiciones son las siguientes:

Saltar una piedra, con un costo de $|\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}|)$
Saltar dos piedras, con un costo de $|\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}|)$

Podemos empezar con el caso base $\texttt{dp}[0] = 0$ , porque la rana ya está en esa casilla, y proceder a calcular $\texttt{dp}[1], \texttt{dp}[2], \ldots \texttt{dp}[N - 1]$ .

C++JavaPython


#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] es el costo mínimo para llegar a la N-ésima piedra
	vector<int> dp(N, INT_MAX);
	// dp[0] = 0 es el caso base porque ya estamos en la primera piedra
	dp[0] = 0;
 
	// para cada estado, calcular los estados a los que lleva
	for (int i = 0; i < N - 1; i++) {
		// saltar una piedra
		dp[i + 1] = min(dp[i + 1], dp[i] + abs(height[i] - height[i + 1]));
		// saltar dos piedras
		if (i + 2 < N) {
			dp[i + 2] = min(dp[i + 2], dp[i] + abs(height[i] - height[i + 2]));
		}
	}
 
	cout << dp[N - 1] << endl;
}


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(); }
 
		// dp[N] es el costo mínimo para llegar a la N-ésima piedra
		int[] dp = new int[N];
		Arrays.fill(dp, Integer.MAX_VALUE);
		// dp[0] = 0 es el caso base porque ya estamos en la primera piedra
		dp[0] = 0;
 
		// para cada estado, calcular los estados a los que lleva
		for (int i = 0; i < N - 1; ++i) {
			// saltar una piedra
			dp[i + 1] =
			    Math.min(dp[i + 1], dp[i] + Math.abs(height[i] - height[i + 1]));
			// saltar dos piedras
			if (i + 2 < N) {
				dp[i + 2] =
				    Math.min(dp[i + 2], dp[i] + Math.abs(height[i] - height[i + 2]));
			}
		}
 
		System.out.println(dp[N - 1]);
	}
 
	// CodeSnip{Kattio}
}


stone_num = int(input())
# height está indexado desde 1 para alinearlo con dp
height = [0] + [int(s) for s in input().split()]
assert stone_num == len(height) - 1
 
"""
dp[N] es el costo mínimo para llegar a la N-ésima piedra
(inicialmente ponemos todos los valores en INF)
"""
dp = [float("inf") for _ in range(stone_num + 1)]
# dp[1] = 0 es el caso base porque ya estamos en la primera piedra
dp[1] = 0
 
for i in range(1, stone_num + 1):
	if i + 1 <= stone_num:
		dp[i + 1] = min(dp[i + 1], dp[i] + abs(height[i] - height[i + 1]))
	if i + 2 <= stone_num:
		dp[i + 2] = min(dp[i + 2], dp[i] + abs(height[i] - height[i + 2]))
 
print(dp[stone_num])

Pull DP

Hay dos formas de llegar a la piedra $i$ : desde la piedra $i - 1$ y desde la piedra $i - 2$ .

Saltar desde la piedra $i - 1$ , con un costo de $|\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}|)$
Saltar desde la piedra $i - 2$ , con un costo de $|\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}|)$

Podemos empezar con el caso base $\texttt{dp}[0] = 0$ , porque la rana ya está en esa casilla, y proceder a calcular $\texttt{dp}[1], \texttt{dp}[2], \ldots \texttt{dp}[N - 1]$ .

C++JavaPython


#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] es el costo mínimo para llegar a la N-ésima piedra
	vector<int> dp(N, INT_MAX);
	// dp[0] = 0 es el caso base porque ya estamos en la primera piedra
	dp[0] = 0;
 
	// para cada estado, procesar los estados que llevan a él
	for (int i = 1; i < N; i++) {
		// saltar una piedra
		if (i - 1 >= 0) {
			dp[i] = min(dp[i], dp[i - 1] + abs(height[i] - height[i - 1]));
		}
		// saltar una piedra
		if (i - 2 >= 0) {
			dp[i] = min(dp[i], dp[i - 2] + abs(height[i] - height[i - 2]));
		}
	}
 
	cout << dp[N - 1] << endl;
}


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(); }
 
		// dp[N] es el costo mínimo para llegar a la N-ésima piedra
		int[] dp = new int[N];
		Arrays.fill(dp, Integer.MAX_VALUE);
		// dp[0] = 0 es el caso base porque ya estamos en la primera piedra
		dp[0] = 0;
 
		// para cada estado, procesar los estados que llevan a él
		for (int i = 1; i < N; ++i) {
			// saltar una piedra
			if (i - 1 >= 0) {
				dp[i] =
				    Math.min(dp[i], dp[i - 1] + Math.abs(height[i] - height[i - 1]));
			}
			// saltar dos piedras
			if (i - 2 >= 0) {
				dp[i] =
				    Math.min(dp[i], dp[i - 2] + Math.abs(height[i] - height[i - 2]));
			}
		}
 
		System.out.println(dp[N - 1]);
	}
 
	// CodeSnip{Kattio}
}


N = int(input())
height = [int(s) for s in input().split()]
 
"""
dp[N] es el costo mínimo para llegar a la N-ésima piedra
(inicialmente ponemos todos los valores en INF)
"""
dp = [float("inf") for _ in range(N)]
# dp[0] = 0 es el caso base porque ya estamos en la primera piedra
dp[0] = 0
 
# para cada estado, procesar los estados que llevan a él
for i in range(1, N):
	# saltar una piedra
	if i - 1 >= 0:
		dp[i] = min(dp[i], dp[i - 1] + abs(height[i] - height[i - 1]))
	# saltar dos piedras
	if i - 2 >= 0:
		dp[i] = min(dp[i], dp[i - 2] + abs(height[i] - height[i - 2]))
 
print(dp[N - 1])

Problemas clásicos

Los próximos módulos dan ejemplos de algunos problemas clásicos: problemas de programación dinámica que son muy conocidos. Sin embargo, clásico no implica necesariamente frecuente. Como tantos competidores conocen estos problemas, los problemsetters rara vez proponen aplicaciones directas de ellos.

Conjuntos de problemas

Recursos
Fuente	Recurso	Notas
CSES	DP Section	Hay que saber hacer todos estos al terminar la sección de DP. Hay editoriales aquí .
AC	DP Contest	Algunas tareas están más allá del alcance de Oro. Hay editoriales aquí .
CF	Beginner DP Contest	Problemas clásicos amigables para principiantes. Algunas tareas piden archivos de entrada/salida. El código de las soluciones está aquí y aquí .
CF	DP Practice Problems	Buenos problemas de práctica. Se debería poder hacer la mayoría después de completar el módulo de DP de Oro. Algunos problemas pueden estar más allá del alcance de Oro.

Algunos de estos problemas se mencionan en los próximos módulos.

Problemas introductorios

Problemas más fáciles que no piden tantas optimizaciones ni estados complejos.

Fuente	Nombre	Dificultad	Tags	Solución
CF	Mortal Kombat Tower	Fácil	DP	Solución
CF	Increasing Frequency	Fácil	DP	Solución
Gold	Hoof Paper Scissors	Fácil	DP	Solución
Gold	★ Time is Mooney	Fácil	DP	Solución
Gold	Teamwork	Normal	DP	Solución
Gold	Snakes	Normal	DP	Solución
IOI	Phidias	Normal	DP	Solución
CF	Moving to the Capital	Difícil	DP, BFS	Solución

USACO más difíciles

Fuente	Nombre	Dificultad	Tags	Solución
Gold	★ Circular Barn Revisited	Difícil	DP	Solución
Gold	Taming the Herd	Difícil	DP	Solución
Gold	Drought	Difícil	DP, Prefix Sums	Solución
Gold	Moortal Cowmbat	Difícil	DP, Prefix Sums, APSP	Solución
Platinum	Team Building	Difícil	DP	Solución
Gold	Stamp Painting	Muy difícil	DP	Solución
Gold	Bovine Genetics	Muy difícil	DP	—
Gold	Interstellar Intervals	Muy difícil	DP, Prefix Sums	—