DP de intervalos
Tema: Programación Dinámica · temarios: Syllabus OCI · Syllabus IOI
📍 Dónde se aprende: módulo 22 de la Ruta de Aprendizaje.
El problema: juntar montones vecinos pagando por cada fusión
Hay tres montones con pesos [4,1,3]. En cada paso podemos juntar dos montones
adyacentes; pagamos la suma de sus pesos y dejamos un solo montón con ese peso.
Queremos acabar con uno minimizando el costo total acumulado.
Si juntamos primero 4 y 1, pagamos 5 y luego 8: total 13. Si juntamos primero 1 y 3, pagamos 4 y luego 8: total 12. El peso final siempre es 8, pero el orden cambia cuánto pagamos antes de llegar a él.
Si el diagrama no cabe, deslízalo horizontalmente.
Cada montón intermedio representa un intervalo del arreglo original. Eso sugiere el estado dp[l][r] = costo mínimo de convertir las posiciones l…r en un solo montón, con índices desde 0 y ambos extremos incluidos.
Pensar en la última decisión
Antes de la última fusión del intervalo [l,r] deben quedar dos montones:
uno que contiene [l,k] y otro que contiene [k+1,r], para algún corte l≤k<r.
Prepararlos cuesta dp[l][k] + dp[k+1][r]. Juntarlos al final cuesta la suma
de todos los pesos de [l,r], independientemente del corte.
dp[l][r] = mínimo sobre k de (dp[l][k] + dp[k+1][r]) + suma(l,r).
Si una preparación no fuera óptima para su intervalo, podríamos reemplazarla por otra más barata sin cambiar la última fusión. Esa observación justifica usar las respuestas óptimas pequeñas. Probar todos los cortes cubre todas las posibles últimas decisiones. El caso base es dp[i][i]=0: un montón ya está unido.
Llenar primero los intervalos pequeños
| Longitud | Estado | Cálculo | Resultado |
|---|---|---|---|
| 1 | [0,0], [1,1], [2,2] | no requieren fusionar | 0 |
| 2 | [0,1] | 0 + 0 + 4 + 1 | 5 |
| 2 | [1,2] | 0 + 0 + 1 + 3 | 4 |
| 3 | [0,2], corte después de 0 | 0 + 4 + 8 | 12 |
| 3 | [0,2], corte después de 1 | 5 + 0 + 8 | 13 |
La respuesta es el mínimo de las dos últimas alternativas, 12. Recorrer longitudes crecientes garantiza que ambos subintervalos ya estén resueltos. No es el único orden válido: también puede recorrerse l de mayor a menor y r de menor a mayor. Lo esencial es respetar las dependencias.
Implementación de dos problemas de intervalos
// Largos crecientes: un orden que resuelve antes los subintervalos necesarios.
// Ejemplo: costo mínimo de juntar montones adyacentes, donde juntar dos cuesta
// la suma de lo que contienen.
long long juntar(const vector<long long>& a) {
int n = a.size();
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
vector<vector<long long>> dp(n, vector<long long>(n, 0));
for (int largo = 2; largo <= n; largo++) // ← el orden que importa
for (int l = 0; l + largo - 1 < n; l++) {
int r = l + largo - 1;
dp[l][r] = LLONG_MAX;
for (int k = l; k < r; k++) // dónde parto el intervalo
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
dp[l][r] += pre[r + 1] - pre[l]; // juntar los dos trozos
}
return dp[0][n - 1];
}
// Juego de dos: por turnos sacan el extremo izquierdo o el derecho, ambos juegan
// óptimo. dp[l][r] = la mayor DIFERENCIA (yo - rival) que logra quien parte.
long long juego(const vector<long long>& a) {
int n = a.size();
vector<vector<long long>> dp(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++) dp[i][i] = a[i];
for (int largo = 2; largo <= n; largo++)
for (int l = 0; l + largo - 1 < n; l++) {
int r = l + largo - 1;
// tomo un extremo y le paso el turno: su ventaja es mi desventaja
dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1]);
}
return dp[0][n - 1];
}juntar({4,1,3}) devuelve 12. La función calcula primero sumas acumuladas:
pre[i] guarda los primeros i pesos. Así pre[r+1] - pre[l] obtiene el peso
de [l,r] en O(1); en el ejemplo pre vale [0,4,5,8].
Esta tabla auxiliar ahorra repetir la suma en cada estado.
Hay O(n²) intervalos y hasta O(n) cortes por intervalo: O(n³) tiempo,
O(n²) memoria. El arreglo debe ser no vacío y los costos calculados deben
caber en long long. El modelo de montones presupone pesos no negativos.
Otro problema: elegir extremos contra un rival
La segunda función del bloque resuelve un juego diferente. Dos personas alternan turnos; en cada turno toman el valor del extremo izquierdo o derecho. Ambas buscan maximizar su puntaje final. Después de elegir un extremo, lo que queda también es un intervalo.
Ahora definimos dp[l][r] = máxima diferencia (puntaje propio − puntaje rival)
que puede obtener quien tiene el turno en ese intervalo.
Si tomamos a[l], el rival recibe el turno y logra una ventaja dp[l+1][r].
Su ventaja se resta de la nuestra. Lo mismo ocurre al tomar a[r]:
dp[l][r] = max(a[l] − dp[l+1][r], a[r] − dp[l][r−1]).
El caso base es dp[i][i]=a[i], porque queda un solo valor y lo toma quien juega.
Para [4,1,3], los intervalos de longitud 2 tienen diferencias 3 y 2.
La respuesta completa es max(4−2, 3−3) = 2. Así juego({4,1,3}) devuelve
2, no el puntaje del primero. Como la suma total es 8, ese puntaje es
(8+2)/2 = 5; el otro obtiene 3.
Este juego usa O(n²) tiempo y memoria: solo dos alternativas por estado. Requiere un arreglo no vacío y valores cuyas diferencias y sumas no desborden. Puede admitir valores negativos: el estado sigue midiendo la diferencia desde el punto de vista de quien tiene el turno.
Errores que revela la definición del estado
En la fusión, iniciar el intervalo vacío de decisiones en cero inventaría
una alternativa gratuita; por eso se inicia en LLONG_MAX antes de minimizar.
En el juego, sumar la ventaja del rival en lugar de restarla cambiaría quién
recibe el beneficio. Ambos errores se detectan volviendo al significado de dp.
¿Por qué no elegir siempre el extremo mayor en el juego?
En [8,15,3,7], elegir 8 permite al rival tomar 15 y terminar ganando. Elegir 7 garantiza poder tomar 15 después: obtenemos 22 frente a 11. La decisión depende del juego que dejamos al rival, no solo del premio inmediato.
Para reconstruir fusiones, guarda el corte elegido junto al costo y recorre
esos cortes desde [0,n−1]. Con condiciones adicionales demostradas,
Optimización de Knuth acelera ciertas recurrencias de fusión; no se aplica
automáticamente a cualquier DP de intervalos. La memoria de una tabla de
long long de n×n requiere aproximadamente 8n² bytes, además de sus contenedores.