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 actualDecisiónEstado anterior
D(2,5)=7tomar el objeto (3,4)D(1,2)=3
D(1,2)=3tomar 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 xlower_bound apunta aqué hacecola después
3el finalextiende{3}
1el 3reemplaza{1}
4el finalextiende{1, 4}
1el 1reemplaza (por sí mismo){1, 4}
5el finalextiende{1, 4, 5}
9el finalextiende{1, 4, 5, 9}
2el 4reemplaza{1, 2, 5, 9}
6el 9reemplaza{1, 2, 5, 6}
3011421354952667auna LIS: 1 4 5 9 (largo 4), las casillas marcadas1256colacola[k] = el menor final posiblede una subsecuencia de largo k + 1cola.size() = 4 es la respuesta; pero 1 2 5 6 NO es una subsecuencia (el 2 está después del 5)

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.

Fusionar [4, 1, 3]: probar cada último corte401132[4] | [1, 3]0 + 4 + 8 = 12[4, 1] | [3]5 + 0 + 8 = 13dp[0][2] = min(12, 13) = 12Cada candidato combina dp[l][k] y dp[k+1][r].Ambos tramos son menores: calcular por longitud creciente.

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.

1011bit 3bit 2bit 1bit 0mask == 11 → {0, 1, 3}bit k = 1: incluye k(mask >> k) & 1¿está el k?mask | (1 << k)agregar el k2ⁿ subconjuntos; dp[mask][v] puede tener n·2ⁿ estados

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:

EstadoQué cuentaCantidad
dp[0b001][0]01
dp[0b011][1]0 → 11
dp[0b101][2]0 → 21
dp[0b111][2]0 → 1 → 21

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.

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?

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
1⭐ La torre de la maldadNacional 2021DP de intervalos con reconstrucción
2⭐ Los Fideos de MaríaRegional 2025diseñar el estado correcto
3⭐ La biblioteca ChipotleNacional 2018word-break: DP sobre un texto

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1Book Shop (CSES 1158)★★★ (—)mochila 0/1 canónica
2Increasing 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?


← 21 - Árboles I · Ruta de Aprendizaje · 23 - Greedy demostrable →