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;
i01234567
formas[i]11248163263
1011224384165?6formas+5+4+3+2+1formas[5] = formas[4] + formas[3] + formas[2] + formas[1] + formas[0]= 8 + 4 + 2 + 1 + 1 = 16“+k” es la última tirada: si salió k, justo antes había que estar sumando 5 − k

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

  1. Estado: ¿qué significa dp[i]? (la decisión más importante de todas)
  2. Transición: ¿cómo se calcula desde estados menores?
  3. Casos base: ¿dónde parte?
  4. 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:

Sumar 6: probamos la última monedaÚltimaRestoTotal16 − 1 = 52 + 1 = 336 − 3 = 31 + 1 = 246 − 4 = 22 + 1 = 3Total = mejor[resto] + 1 moneda.Mínimo: 2 monedas, eligiendo 3 + 3.

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:

icandidatos mejor[i - m] + 1mejor[i]
1m=1: 0+11
2m=1: 1+12
3m=1: 2+1 · m=3: 0+11
4m=1: 1+1 · m=3: 1+1 · m=4: 0+11
5m=1: 1+1 · m=3: 2+1 · m=4: 1+12
6m=1: 2+1 · m=3: 1+1 · m=4: 2+12

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 / capacidad012345
ninguno: D(0,c)000000
solo (2,3): D(1,c)003333
ambos: D(2,c)003447

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:

objeto: peso 3, valor 5 · dp antes = todo 0Hacia atrás: justo después de c = 60001020304055657dp[6] lee dp[3], que aún vale 0 → 0 + 5cada casilla lee la versión “sin este objeto” de la de más a la izquierda: entra una sola vez❌ c de 3 hacia 7 (hacia adelante)000102535455106107dp[6] lee dp[3], que YA vale 5 → 5 + 5dp[6] = 10 significa “el objeto dos veces”: eso es la mochila ilimitada, otro problema

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í
}
ia[i]actual (empezar de nuevo vs seguir)mejor
0−2−2−2
13max(3, −2 + 3) = 3 → empieza de nuevo3
2−1max(−1, 3 − 1) = 2 → sigue3
34max(4, 2 + 4) = 6 → sigue6
4−5max(−5, 6 − 5) = 1 → sigue6

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.

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.

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):

#ProblemaFaseQué practica
1El mejor caminoNacional 2021DP de grilla con doble costo
2ParkourNacional 2022DP capa por capa
3Alcohol GelRegional 2021Kadane con reconstrucción
4⭐ Descenso en parapenteRegional 2021mínimos sufijos en 2D
5⭐⭐ GalletasNacional 2025DP de juegos: la ficha posiciones ganadoras te da lo que falta

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1Dice Combinations (CSES 1633)★★ (—)el clásico 1, tal cual
2Minimizing Coins (CSES 1634)★★ (—)el clásico 2, tal cual
3Long Jumps (1472C)★★ (1100)DP sobre saltos hacia adelante
4Cut 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";

← 13 - Backtracking · Ruta de Aprendizaje · 15 - Grafos I - BFS y DFS →