22 · Programación dinámica II
Estructuras y algoritmos avanzados · Ruta de Aprendizaje
Antes de empezar. Estados y transiciones: 14 - Programación dinámica I; lower_bound: 08 - Búsqueda binaria; para máscaras, bits de 20 - Fenwick y segment tree.
🎯 Objetivos
Al terminar este módulo sabes:
- Repasar mochila 0/1 y reconstruir una elección usando la tabla por etapas.
- Calcular la LIS en O(n log n).
- Reconocer los estados menos obvios: intervalos y máscaras de bits.
📖 La lección
Hay tres ideas nuevas, que puedes estudiar por separado: mejores finales para LIS, intervalos y subconjuntos. Mochila abre como repaso y puente a la reconstrucción.
Mochila 0/1: por qué se recorre la capacidad hacia atrás
Cada objeto tiene peso y valor y se puede elegir a lo más una vez.
D(i, c) es el mejor valor usando los primeros i objetos y capacidad c.
Para el objeto de peso w y valor v, hay dos opciones: no tomarlo, con valor
D(i-1, c), o tomarlo, con valor D(i-1, c-w) + v si cabe. Elegimos el máximo.
Sin objetos, el valor es cero; no es obligatorio llenar la mochila.
Solo necesitamos la fila anterior, por lo que podemos guardar un vector
dp[c]. Al recorrer c de mayor a menor, dp[c-w] todavía pertenece a la
fila anterior. Hacerlo al revés permitiría tomar el mismo objeto de nuevo.
// supone: int C; vector<int> peso, valor; // C >= 0, pesos > 0, mismo tamaño
vector<long long> dp(C + 1, 0);
for (int i = 0; i < (int)peso.size(); i++)
for (int c = C; c >= peso[i]; c--)
dp[c] = max(dp[c], dp[c - peso[i]] + valor[i]);
cout << dp[C] << "\n";Con un único objeto de peso 2 y valor 3 y capacidad 4, la respuesta es 3.
Si recorrieras hacia adelante, primero harías dp[2] = 3 y después
dp[4] = dp[2] + 3 = 6: habrías inventado una segunda copia.
El tiempo es O(n·C), la memoria O(C), y los valores acumulados deben caber
en long long. La ficha Mochila 0-1 desarrolla más ejemplos y
la reconstrucción de los objetos elegidos.
Reconstruir cuáles objetos se eligieron
La tabla conserva las etapas. Con la tabla D(i,c) del módulo 14, empieza en D(n,C). Si D(i,c)=D(i−1,c), puedes no elegir el objeto i−1 y bajar a esa fila; si difieren, elige ese objeto y continúa en D(i−1,c−peso[i−1]). Con (2,3),(3,4) y C=5, pasas de D(2,5)=7 a D(1,2)=3 tomando el segundo, y a D(0,0)=0 tomando el primero. En empate basta elegir una solución óptima. La tabla completa permite reconstruir; comprimirla exige conservar información adicional.
| Estado actual | Decisión | Estado anterior |
|---|---|---|
| D(2,5)=7 | tomar el objeto (3,4) | D(1,2)=3 |
| D(1,2)=3 | tomar el objeto (2,3) | D(0,0)=0 |
El valor de la fila anterior es la comparación que decide si podemos omitir el objeto. Si lo tomamos, restamos su peso a la capacidad, no su valor. Al avanzar hacia atrás en i nunca reutilizamos un objeto. Para programarlo, usa la tabla D construida en el módulo 14, no el vector comprimido:
// supone: int n, C; vector<int> peso; vector<vector<long long>> D;
vector<int> elegidos;
int capacidad = C;
for (int i = n; i > 0; i--) {
if (D[i][capacidad] == D[i - 1][capacidad]) continue;
elegidos.push_back(i - 1);
capacidad -= peso[i - 1];
}
reverse(elegidos.begin(), elegidos.end());elegidos contiene índices desde cero. En el ejemplo son 0 y 1. Si hay
varias soluciones óptimas, el empate permite omitir el objeto y reconstruir
una de ellas.
LIS en O(n log n): DP + búsqueda binaria
Una subsecuencia conserva el orden original, pero puede saltarse
posiciones. En {3, 1, 4, 2, 5}, {1, 2, 5} es creciente; {1, 5, 4}
no respeta el orden y además no crece. Aquí «creciente» significa estrictamente:
no se permiten valores iguales consecutivos.
La DP inicial define D[i] como el mayor largo que termina en i.
Parte en 1 y prueba cada j < i con a[j] < a[i]: puede extender esa
subsecuencia y obtener D[j] + 1. Esto cuesta O(n²).
Con {3,1,4,2,5}, los estados D son {1,1,2,2,3}: el 4 extiende al 3 o al 1; el 2 solo al 1; el 5 puede extender una subsecuencia de largo 2. La respuesta es el máximo de D, no necesariamente su última casilla.
Para largo 2, terminar en 2 permite todas las extensiones que permite terminar en 4, y quizás más. Basta conservar el final 2 para decidir largos futuros; no hace falta conservar las dos subsecuencias completas.
Para acelerarlo, conservaremos el menor final para cada largo: un final más pequeño ofrece al menos las mismas posibilidades de extensión.
Por qué sirve buscar el primer final mayor o igual
Los menores finales están estrictamente ordenados. Si existe una subsecuencia creciente de largo k+1, al quitarle su último elemento queda una de largo k con un final menor. El menor final de largo k no puede ser mayor que ese final. Por eso el mínimo para largo k es menor que el mínimo para largo k+1.
Al llegar x, sea p la primera posición de cola cuyo valor es ≥ x:
- Si p=0, x mejora el final de una subsecuencia de largo 1.
- Si p>0,
cola[p−1] < x: existe una subsecuencia de largo p que podemos extender con el x recién llegado. Su nuevo largo es p+1. - No podemos extender una de largo p+1: su menor final ya es ≥ x. Los finales posteriores tampoco permiten hacerlo. Solo esa casilla cambia.
- Si no hay final ≥ x, podemos extender la más larga y agregar una casilla.
Con finales {1,4,5,9} y x=2, extendemos el final 1 y mejoramos el de largo
2, de 4 a 2. No podemos extender el de largo 2 anterior porque terminaba
en 4. Los otros finales permanecen válidos como respuestas de etapas anteriores.
Si x coincide con un final, lo reemplaza sin aumentar el largo: así exigimos
crecimiento estricto. lower_bound encuentra precisamente esa frontera.
// supone: vector<int> a; // el arreglo
vector<int> cola; // cola[k] = menor final posible de una subsecuencia de largo k+1
for (int x : a) {
auto it = lower_bound(cola.begin(), cola.end(), x);
if (it == cola.end()) cola.push_back(x); // extiende la más larga
else *it = x; // mejora un final existente
}
cout << cola.size() << "\n";Traza con a = {3, 1, 4, 1, 5, 9, 2, 6}:
llega x | lower_bound apunta a | qué hace | cola después |
|---|---|---|---|
| 3 | el final | extiende | {3} |
| 1 | el 3 | reemplaza | {1} |
| 4 | el final | extiende | {1, 4} |
| 1 | el 1 | reemplaza (por sí mismo) | {1, 4} |
| 5 | el final | extiende | {1, 4, 5} |
| 9 | el final | extiende | {1, 4, 5, 9} |
| 2 | el 4 | reemplaza | {1, 2, 5, 9} |
| 6 | el 9 | reemplaza | {1, 2, 5, 6} |
Si el diagrama no cabe, deslízalo horizontalmente.
El invariante dice que cola guarda, para cada largo, el final más chico visto.
Adapta el argumento: explica qué cambia si la subsecuencia permite iguales.
Y la trampa que la figura deja a la vista: cola no es la subsecuencia, solo el mejor final
posible de cada largo. Su tamaño es la respuesta; para recuperar la
subsecuencia real hay que guardar más (está en la ficha). Ficha completa (incluida
la reconstrucción): Subsecuencia creciente más larga (LIS).
Intervalos: fusionar bloques
Queremos fusionar bloques contiguos de tamaños {4, 1, 3}.
Cada fusión cuesta la suma de los bloques que une. dp[l][r] es el costo
mínimo de fusionar ese intervalo en un bloque; dp[i][i] = 0.
Si la última unión separa en k, el costo es
dp[l][k] + dp[k+1][r] + suma(l..r). Probamos todos los cortes.
Primero salen dp[0][1] = 5 y dp[1][2] = 4. Para el intervalo completo,
el corte tras 0 cuesta 0 + 4 + 8 = 12; tras 1, 5 + 0 + 8 = 13.
Gana 12: unir primero 1 y 3, luego el 4 restante. El orden por largos
garantiza que ambos intervalos pequeños ya estén resueltos. Hay O(n²)
estados y O(n) cortes por estado: O(n³), usando prefijos para las sumas.
Si el diagrama no cabe, deslízalo horizontalmente.
Ahora implementamos esa recurrencia. Suponemos 0≤n≤300, pesos enteros
positivos de hasta 10⁶; la suma total y el costo caben en long long.
La lista vacía tiene costo cero, y un único bloque no necesita fusiones.
long long fusionar(const vector<int>& a) {
int n = a.size();
if (n == 0) return 0;
vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i];
vector<vector<long long>> dp(n, vector<long long>(n, 0));
for (int largo = 2; largo <= n; largo++) {
for (int l = 0; l + largo <= n; l++) {
int r = l + largo - 1;
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++)
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]
+ pref[r + 1] - pref[l]);
}
}
return dp[0][n - 1];
}En main, cout << fusionar({4,1,3}) imprime 12. Solo leemos intervalos
más cortos, ya calculados. Este estado resuelve fusiones de vecinos;
los juegos donde se retiran extremos necesitan otra transición, desarrollada
en DP de intervalos.
Subconjuntos como estado
Queremos contar rutas que parten de 0 y visitan cada nodo exactamente una vez. Saber solo dónde estamos no basta: también importa qué nodos ya usamos. Guardaremos ese conjunto mediante bits: el bit v vale 1 si v ya está visitado. Un entero que representa así un conjunto se llama máscara.
Si el diagrama no cabe, deslízalo horizontalmente.
En C++ escribimos 0b011 para el conjunto {0,1}; vale 3. Sin el prefijo
0b, 011 sería octal y valdría 9. Los operadores se explican en
la ampliación de bits.
Una máscara con significado concreto. En un grafo de tres nodos
0, 1, 2, el bit v indica si visitamos v: 101 representa {0, 2}.
Para contar caminos que parten de 0 y visitan cada nodo exactamente una vez,
dp[mask][v] cuenta los que usan exactamente mask y terminan en v.
El inicio es dp[0b001][0] = 1; los demás estados empiezan en cero.
Desde un estado, por cada arista v → u cuyo bit u esté apagado, agregamos
dp[mask][v] a dp[mask | (1 << u)][u]. Solo se visita un nodo nuevo,
así que el conjunto crece y la transición no vuelve al estado anterior.
Con aristas 0 → 1, 0 → 2, 1 → 2, aparecen:
| Estado | Qué cuenta | Cantidad |
|---|---|---|
dp[0b001][0] | 0 | 1 |
dp[0b011][1] | 0 → 1 | 1 |
dp[0b101][2] | 0 → 2 | 1 |
dp[0b111][2] | 0 → 1 → 2 | 1 |
La respuesta es la suma sobre los posibles finales con máscara 111:
un camino. Hay 2ⁿ·n estados y hasta n transiciones por estado; esa
memoria exponencial limita el tamaño de n (alrededor de 20, según el límite
y el tipo guardado). Implementemos el caso descrito con un grafo dirigido sin aristas repetidas,
1≤n≤20, representado por listas de vecinos 0..n−1. Contaremos módulo 10⁹+7:
int caminos_todos(const vector<vector<int>>& ady) {
int n = ady.size(), total = 1 << n;
const int MOD = 1000000007;
vector<vector<int>> dp(total, vector<int>(n, 0));
dp[1][0] = 1; // solo hemos visitado 0 y estamos allí
for (int mask = 1; mask < total; mask++) {
for (int v = 0; v < n; v++) {
if (dp[mask][v] == 0) continue;
for (int u : ady[v]) {
if ((mask & (1 << u)) != 0) continue;
int nueva = mask | (1 << u);
dp[nueva][u] = (dp[nueva][u] + dp[mask][v]) % MOD;
}
}
}
int respuesta = 0;
for (int v = 0; v < n; v++) respuesta = (respuesta + dp[total - 1][v]) % MOD;
return respuesta;
}Agregar un bit apagado aumenta el entero mask, por lo que las transiciones
siempre escriben en una máscara que se procesará después. Con
ady={{1,2},{2},{}}, caminos_todos(ady) devuelve 1: solo 0→1→2 visita todos.
El inicio es fijo, pero el destino es libre. DP con bitmask desarrolla
otras variantes. Cada suma modular combina dos enteros menores que MOD,
por lo que cabe en un int de 32 bits.
Con n=20, n·2ⁿ son 20 971 520 casillas: unos 80 MiB usando enteros de 4 bytes o 160 MiB usando 8, sin contar otras estructuras ni el costo del vector de filas. No son solo un millón de estados; comprueba el límite de memoria antes de reservar la tabla.
En Hamiltonian Flights, el destino también está fijado: usando índices desde cero, la respuesta es dp[(1<<n)-1][n-1], no la suma sobre finales. Las cantidades se calculan módulo 10⁹+7; cada arista disponible aporta una transición. La variante de intervalos Removal Game cambia la recurrencia: allí se retiran extremos y hay dos jugadores, en vez de fusionar todos los cortes.
El hub Programación Dinámica tiene el catálogo completo, incluidas las optimizaciones de nivel IOI (Convex hull trick (Li Chao), Optimización de Knuth, Optimización divide y vencerás (DP) y Aliens trick (optimización lagrangiana)). Son material adicional: no tienen módulo propio y se estudian por problemas concretos — el 24 explica cómo, y cada ficha trae su implementación.
🏋️ Práctica
Práctica directa: Comparar estados
En {3,1,4,2,5}, calcula el largo de LIS: 3. En bloques {4,1,3}, calcula el costo mínimo de fusionar vecinos: 12.
Idea para comprobar tu solución
LIS puede conservar mejores finales por largo; fusiones necesita ambos extremos y todos los últimos cortes. No comparten el mismo significado de dp.
Variación: Repetidos y un camino adicional
Para {2,2,3,1,4}, ¿cuánto mide la subsecuencia estrictamente creciente más
larga? En el grafo del ejemplo de máscaras, agrega 2→1: ¿cuántas rutas
parten de 0 y visitan los tres nodos una vez?
Una pista, si la necesitas
Los dos 2 no pueden ocupar posiciones consecutivas de una subsecuencia estrictamente creciente. En el grafo, el conjunto visitado limita los movimientos aunque ahora haya un ciclo.
Contrastar el razonamiento
La LIS mide 3: 2,3,4. El segundo 2 reemplaza el mismo final, no lo extiende. Hay dos rutas: 0→1→2 y 0→2→1. La máscara impide volver a un nodo usado, por lo que el ciclo 1→2→1 no crea rutas adicionales.
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 | ⭐ La torre de la maldad | Nacional 2021 | DP de intervalos con reconstrucción |
| 2 | ⭐ Los Fideos de María | Regional 2025 | diseñar el estado correcto |
| 3 | ⭐ La biblioteca Chipotle | Nacional 2018 | word-break: DP sobre un texto |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Book Shop (CSES 1158) | ★★★ (—) | mochila 0/1 canónica |
| 2 | Increasing Subsequence (CSES 1145) | ★★★ (—) | LIS n log n, tal cual |
| 3 | ⭐ Removal Game (CSES 1097) | ★★★★ (—) | DP de intervalos con dos jugadores |
| 4 | ⭐ Hamiltonian Flights (CSES 1690) | ★★★★★ (—) | bitmask + grafos: la boda completa |
Para pensar: los mejores finales no forman una subsecuencia
Procesa {2, 6, 3, 4, 1} con el algoritmo de LIS. Al terminar,
cola = {1, 3, 4}. ¿Es esa una subsecuencia del arreglo original?
¿Por qué su tamaño sigue dando la respuesta correcta?
Ver razonamiento
No es una subsecuencia: el 1 aparece después del 3 y del 4. Cada posición resume una afirmación distinta: existe una subsecuencia de largo 1 que termina en 1, una de largo 2 que termina en 3 (
2, 3) y una de largo 3 que termina en 4 (2, 3, 4). El nuevo 1 mejora el final para largo 1 sin borrar la existencia de las otras.colaguarda los menores finales posibles, no una única cadena de elecciones. Su largo es 3; para reconstruir una LIS hacen falta índices y predecesores adicionales.
← 21 - Árboles I · Ruta de Aprendizaje · 23 - Greedy demostrable →