14 · Programación dinámica I
Buscar soluciones eficientes · Ruta de Aprendizaje
Antes de empezar. Recursión y memoización: 09 - Recursión; arreglos y matrices: 03 - Arreglos y búsqueda lineal y 04 - Matrices. El ejemplo de dados usa el resto de una suma, explicado en aritmética modular.
🎯 Objetivos
Al terminar este módulo sabes:
- Reconocer cuándo un problema “huele a DP”.
- Aplicar la receta: estado → transición → casos base → orden.
- Resolver los tres clásicos fundacionales: conteo de secuencias de dados, monedas y mochila.
📖 La lección
Qué es (y de dónde viene)
En el módulo 09 viste que memorizar resultados bajó fib(30) de millones de llamadas a 59. La programación dinámica es esa idea hecha método: sirve cuando el problema tiene subproblemas que se repiten y la respuesta grande se arma con respuestas chicas. Hay dos estilos equivalentes: top-down (recursión + memo) y bottom-up (llenar una tabla en orden) — el de la tabla suele ser más rápido y más fácil de razonar.
El recorrido de la clase va de contar secuencias a minimizar monedas y elegir objetos. Kadane queda como una aplicación posterior.
Clásico 1: contar formas (dados)
¿De cuántas formas sumas n tirando dados 1..6? Estado: formas[i] = formas
de sumar exactamente i. El orden importa: 1+2 y 2+1 son
dos secuencias distintas. Suponemos n >= 0.
La solución directa enumera cada secuencia. Para n=3 aparecen 111, 12, 21 y 3. Pero al buscar secuencias más largas se vuelve a preguntar muchas veces cuántas formas completan una misma suma pendiente.
Define F(0)=1 y F(i)=Σ F(i−d), para caras d≤i. La recursión evalúa esa fórmula bajando a sumas menores; memoizar guarda cada F(i) la primera vez; tabular calcula F(0), F(1), … en ese orden. No cambia la pregunta: cambia cuándo se guarda la respuesta. En F(3), las tres últimas caras posibles aportan F(2)+F(1)+F(0)=2+1+1=4. Como cada secuencia tiene una única última cara, los grupos no se solapan.
// supone: int n; // la suma que queremos formar
const long long MOD = 1000000007; // el enunciado pide la respuesta módulo esto
vector<long long> formas(n + 1, 0);
formas[0] = 1; // una forma de sumar 0: no tirar
for (int i = 1; i <= n; i++)
for (int dado = 1; dado <= 6 && dado <= i; dado++)
formas[i] = (formas[i] + formas[i - dado]) % MOD;i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
formas[i] | 1 | 1 | 2 | 4 | 8 | 16 | 32 | 63 |
Si el diagrama no cabe, deslízalo horizontalmente.
La transición se lee así: la última tirada fue algún dado entre 1 y 6, y
antes de ella había que estar sumando exactamente i - dado. Por eso
formas[7] es 63 y no 64: de las siete casillas anteriores, formas[0] no
cuenta porque el 7 no es una cara del dado.
La receta de 4 pasos
- Estado: ¿qué significa
dp[i]? (la decisión más importante de todas) - Transición: ¿cómo se calcula desde estados menores?
- Casos base: ¿dónde parte?
- Orden: ¿en qué orden se llena para que lo necesario ya esté listo?
El costo es número de estados × trabajo total por estado (incluye probar todas sus transiciones) — chequéalo contra
Complejidad computacional antes de programar.
Clásico 2: el mínimo (monedas)
Mínimo de monedas para sumar x >= 0, con denominaciones positivas y
cantidad ilimitada de cada una. Pensemos primero qué pregunta contesta
cada casilla: mejor[i] es la menor cantidad de monedas que suma exactamente i.
Para sumar cero no usamos ninguna: mejor[0] = 0.
Con monedas {1, 3, 4}, para completar 6 podemos pensar en la última moneda.
Si es un 3, antes teníamos que sumar 3; si es un 4, antes teníamos que sumar 2.
Probamos cada última moneda que no sobrepase i y agregamos una a la mejor
respuesta del resto:
Si el diagrama no cabe, deslízalo horizontalmente.
Toda solución termina en alguna moneda disponible, así que no perdemos opciones.
Para cada última moneda conviene usar la menor cantidad posible en el resto:
usar más solo empeoraría el total. Por eso tomamos el mínimo entre esos candidatos.
Como las monedas son positivas, i - m siempre es menor que i; al calcular
i de menor a mayor, esa respuesta anterior ya está lista.
El INF marca «imposible todavía»; si mejor[x] termina en INF, no hay
forma de construir esa suma. Es un número grande con margen para sumar uno,
no el máximo representable por el tipo:
// supone: int x; vector<int> moneda; // el objetivo y las monedas disponibles
const long long INF = 1e18; // "imposible por ahora"
vector<long long> mejor(x + 1, INF);
mejor[0] = 0;
for (int i = 1; i <= x; i++)
for (int m : moneda)
if (m <= i && mejor[i - m] + 1 < mejor[i])
mejor[i] = mejor[i - m] + 1;Con monedas {1, 3, 4} y x = 6 la traza es:
i | candidatos mejor[i - m] + 1 | mejor[i] |
|---|---|---|
| 1 | m=1: 0+1 | 1 |
| 2 | m=1: 1+1 | 2 |
| 3 | m=1: 2+1 · m=3: 0+1 | 1 |
| 4 | m=1: 1+1 · m=3: 1+1 · m=4: 0+1 | 1 |
| 5 | m=1: 1+1 · m=3: 2+1 · m=4: 1+1 | 2 |
| 6 | m=1: 2+1 · m=3: 1+1 · m=4: 2+1 | 2 |
La respuesta es 2 (3+3) — y nota que el greedy “toma la más grande” habría dicho 3 (4+1+1). Por eso existe la DP: en vez de apostar por una moneda, mira todas y se queda con la mejor.
También hay sumas imposibles: con monedas {3, 4}, mejor[1] y mejor[2]
siguen en INF, y para 5 ninguno de los restos es alcanzable. Para 0, en
cambio, la respuesta es 0 incluso si la lista de monedas está vacía.
Si hay k denominaciones, probamos hasta k opciones en cada una de x sumas:
O(x·k) tiempo y O(x) memoria.
Clásico 3: mochila 0/1 (el jefe del nivel)
n objetos, cada uno con peso y valor, y una capacidad C: ¿el máximo valor
que cabe? Los pesos son enteros positivos, C es no negativa y la suma de valores elegidos debe caber en long long. Cada objeto se usa como máximo una vez. Antes de comprimir memoria, define D(i,c): mejor valor usando solo los primeros i objetos y capacidad c.
Si no eliges el objeto i−1, conservas D(i−1,c). Si cabe y lo eliges, obtienes D(i−1,c−peso[i−1])+valor[i−1]. Ambos candidatos leen la fila anterior, que todavía no contiene ese objeto.
Con objetos (peso,valor)=(2,3),(3,4) y capacidad 5:
| Objetos disponibles / capacidad | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| ninguno: D(0,c) | 0 | 0 | 0 | 0 | 0 | 0 |
| solo (2,3): D(1,c) | 0 | 0 | 3 | 3 | 3 | 3 |
| ambos: D(2,c) | 0 | 0 | 3 | 4 | 4 | 7 |
Para D(2,5), no tomar da 3 y tomar da D(1,2)+4=7. Para D(2,3), tomar da D(1,0)+4=4. La tabla completa cuesta O(n·C) memoria, pero cada fila solo usa la anterior.
Primero, una fila por etapa
La implementación directa conserva la tabla que acabamos de calcular. El índice i cuenta objetos disponibles; el objeto nuevo está en i−1. Una casilla siempre lee de la fila i−1, nunca de su propia fila:
// supone: int n, C; vector<int> peso, valor; // pesos positivos, vectores de tamaño n
vector<vector<long long>> D(n + 1, vector<long long>(C + 1, 0));
for (int i = 1; i <= n; i++) {
for (int c = 0; c <= C; c++) {
D[i][c] = D[i - 1][c]; // no tomar el nuevo objeto
if (peso[i - 1] <= c)
D[i][c] = max(D[i][c],
D[i - 1][c - peso[i - 1]] + valor[i - 1]);
}
}
cout << D[n][C] << "\n";Con los dos objetos anteriores imprime 7. Con capacidad cero o sin objetos, la respuesta es cero. Esta versión requiere O(n·C) tiempo y O(n·C) memoria; conserva las etapas, lo que también permite reconstruir la elección.
Después, reutilizar memoria
Podemos guardar ambas etapas en un arreglo dp[c] si recorremos las capacidades hacia atrás: las casillas pendientes todavía representan D(i−1,c). Después de procesar un objeto, todo el arreglo representa la nueva fila.
// supone: int n, C; vector<int> peso, valor; // leídos antes
vector<long long> dp(C + 1, 0); // dp[c] = mejor valor con capacidad c
for (int i = 0; i < n; i++) // un objeto a la vez
for (int c = C; c >= peso[i]; c--) // ⚠️ la capacidad va HACIA ATRÁS
dp[c] = max(dp[c], dp[c - peso[i]] + valor[i]);
cout << dp[C] << "\n";Por qué hacia atrás, que es la pregunta del módulo: al calcular dp[c]
lees dp[c - peso[i]], y quieres que ese valor sea de antes de considerar
el objeto i. Yendo de C hacia abajo, las casillas de la izquierda todavía
no se tocaron en esta pasada, así que cada objeto se usa a lo más una vez. Si
recorrieras hacia adelante estarías leyendo un valor que ya incluye al objeto
i — y lo meterías dos, tres, infinitas veces (que es exactamente la mochila
ilimitada, otro problema y también útil). Con números, un solo objeto de
peso 3 y valor 5 sobre una mochila vacía de capacidad 7:
Si el diagrama no cabe, deslízalo horizontalmente.
Costo: O(n·C) en tiempo, O(C) en memoria. Las variantes (reconstruir qué
objetos entraron, la versión con dp[i][c]) están en Mochila 0-1, y
Programación Dinámica se convierte desde aquí en tu hub de referencia.
Bonus: el subarreglo de suma máxima (Kadane)
Aparece en la práctica y es la DP más chica que existe: recorres el arreglo preguntándote, en cada posición, ¿me conviene empezar un subarreglo nuevo aquí, o estirar el que traía?
// supone: int n; vector<int> a; // n ≥ 1
long long actual = a[0], mejor = a[0];
for (int i = 1; i < n; i++) {
actual = max((long long)a[i], actual + a[i]); // empezar de nuevo vs seguir
mejor = max(mejor, actual); // el mejor visto hasta aquí
}i | a[i] | actual (empezar de nuevo vs seguir) | mejor |
|---|---|---|---|
| 0 | −2 | −2 | −2 |
| 1 | 3 | max(3, −2 + 3) = 3 → empieza de nuevo | 3 |
| 2 | −1 | max(−1, 3 − 1) = 2 → sigue | 3 |
| 3 | 4 | max(4, 2 + 4) = 6 → sigue | 6 |
| 4 | −5 | max(−5, 6 − 5) = 1 → sigue | 6 |
La respuesta es 6, el subarreglo {3, −1, 4}: valió la pena “cargar” con el −1 porque lo que venía después lo compensaba.
actual es «la mejor suma de un subarreglo que termina en i»; mejor
es la mejor de todas las terminaciones vistas. Al llegar al −5 de la tabla,
actual baja a 1, pero mejor conserva el 6 que terminaba en la posición 3.
Un subarreglo que termina en i empieza allí o prolonga uno que terminaba en
i−1: esas dos posibilidades explican el max, sin enumerar todos los comienzos.
Con {-5, −2, −8}, la respuesta es −2, no 0: hay que elegir al menos un
valor. Inicializar ambas variables con a[0] conserva esa condición.
Si lo que
traías era negativo, arrastrarlo solo resta: conviene empezar en a[i].
El subarreglo debe ser no vacío. Funciona en O(n) con positivos y negativos;
con todos positivos, la respuesta es el arreglo entero. La ficha Kadane (subarreglo de suma máxima) trae además la
versión que te dice dónde está ese subarreglo, que es lo que pide la
práctica.
El radar de DP
Huele a DP cuando: piden contar formas, mínimo/máximo de algo que se construye por etapas, el greedy obvio falla, y n es demasiado grande para backtracking pero cabe una tabla (n ≤ 10⁶ para dp lineal, n·C ≤ ~10⁷ para mochila).
🏋️ Práctica
Práctica directa: Contar antes de optimizar
Con caras de dado 1..6, imprime cuántas secuencias suman n. Para n=3, la salida es 4; para n=0, 1.
Idea para comprobar tu solución
Clasifica por última cara: 111,12,21,3. La secuencia vacía explica el caso base y permite construir las de una tirada.
Variación: Cambiar qué se cuenta
Con pasos de largo 1 o 3, cuenta las secuencias que recorren exactamente 4 unidades. Después calcula el mínimo número de pasos para esa misma distancia.
Una pista, si la necesitas
Una pregunta suma alternativas; la otra elige la más corta.
Contrastar el razonamiento
Las secuencias son 1+1+1+1, 1+3 y 3+1: hay 3. El mínimo es 2 pasos. Para contar, maneras[0]=1 y se suman predecesores válidos; para minimizar, mejor[0]=0 y se toma un mínimo más uno.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Problemas OCI reales, en español (cada nota trae el link a su mirror):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | El mejor camino | Nacional 2021 | DP de grilla con doble costo |
| 2 | Parkour | Nacional 2022 | DP capa por capa |
| 3 | Alcohol Gel | Regional 2021 | Kadane con reconstrucción |
| 4 | ⭐ Descenso en parapente | Regional 2021 | mínimos sufijos en 2D |
| 5 | ⭐⭐ Galletas | Nacional 2025 | DP de juegos: la ficha posiciones ganadoras te da lo que falta |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Dice Combinations (CSES 1633) | ★★ (—) | el clásico 1, tal cual |
| 2 | Minimizing Coins (CSES 1634) | ★★ (—) | el clásico 2, tal cual |
| 3 | Long Jumps (1472C) | ★★ (1100) | DP sobre saltos hacia adelante |
| 4 | Cut Ribbon (189A) | ★★★ (1300) | monedas disfrazado de cinta |
| 5 | ⭐ Buns (106C) | ★★★★ (1700) | mochila real, con receta y todo |
Para pensar: el orden cambia qué problema resuelves
Hay un único objeto de peso 2 y valor 3, y una mochila de capacidad 4.
Con dp inicialmente en cero, ¿qué pasa si actualizas las capacidades de
menor a mayor? ¿Qué cambia al recorrerlas de mayor a menor?
Compara el código y predice su salida antes de ejecutarlo:
vector<int> adelante(5, 0), atras(5, 0);
// A: de menor a mayor. Peso 2, valor 3.
for (int c = 2; c <= 4; c++)
adelante[c] = max(adelante[c], adelante[c - 2] + 3);
// B: de mayor a menor, desde cero.
for (int c = 4; c >= 2; c--)
atras[c] = max(atras[c], atras[c - 2] + 3);
cout << adelante[4] << " " << atras[4] << "\n";Ver razonamiento
Hacia adelante,
dp[2]pasa a valer 3. Al llegar a capacidad 4 se usa ese mismodp[2]y se obtiene 6: el único objeto se contó dos veces. Hacia atrás, al calculardp[4],dp[2]todavía pertenece a la etapa sin ese objeto y vale 0; el resultado es 3. La recurrencia de mochila 0/1 necesita valores de la etapa anterior. Recorrer hacia atrás conserva esa condición aunque ambas etapas compartan el mismo arreglo.
← 13 - Backtracking · Ruta de Aprendizaje · 15 - Grafos I - BFS y DFS →