Data Structure & Algorithms
Dynamic programming: patrones clásicos
Patrones clásicos de dynamic programming en una y dos dimensiones, knapsack, LCS, LIS, grids, intervalos, árboles y bitmasking.
- Última actualización
- Actualizada
- Nivel
- Profundización
Data Structure & Algorithms
Patrones clásicos de dynamic programming en una y dos dimensiones, knapsack, LCS, LIS, grids, intervalos, árboles y bitmasking.
Los problemas clásicos de dynamic programming enseñan formas de diseñar estados y transiciones. El objetivo no es memorizar tablas, sino reconocer qué decisión cambia el futuro y qué información debe conservar el estado.
El estado depende de una posición o cantidad.
Ejemplo: costo mínimo para llegar al escalón i.
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]La transición dice que el último salto solo pudo venir de uno de dos estados anteriores.
Si solo necesitas los dos valores previos, puedes comprimir memoria de O(n) a O(1).
El estado necesita dos dimensiones, como posiciones en dos secuencias o coordenadas de una cuadrícula.
Para prefijos de a y b:
dp[i][j] = longitud de la LCS entre a[0..i) y b[0..j)Si los últimos caracteres coinciden:
dp[i][j] = 1 + dp[i - 1][j - 1]Si no coinciden:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])function lcsLength(a: string, b: string): number {
const rows = a.length + 1;
const cols = b.length + 1;
const dp = Array.from({ length: rows }, () => Array(cols).fill(0));
for (let i = 1; i < rows; i += 1) {
for (let j = 1; j < cols; j += 1) {
dp[i][j] =
a[i - 1] === b[j - 1]
? 1 + dp[i - 1][j - 1]
: Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[a.length][b.length];
}Tiempo: O(nm), porque se llenan n × m estados. Espacio: O(nm) en esta implementación.
Cada elemento puede tomarse una vez o no tomarse.
Estado habitual:
dp[i][capacity] = mejor valor usando los primeros i elementosTransición:
no tomar: dp[i - 1][capacity]
tomar: value[i] + dp[i - 1][capacity - weight[i]]El detalle crítico de la compresión 1D es iterar capacidades de derecha a izquierda. Si avanzas hacia la derecha, reutilizas el mismo objeto varias veces y conviertes accidentalmente el problema 0/1 en unbounded knapsack.
La formulación O(n²) usa:
dp[i] = longitud de la LIS que termina exactamente en iPara cada j < i, si values[j] < values[i], puedes extender la subsecuencia.
Existe una solución O(n log n) con binary search sobre un array de mejores finales. Ese array no representa necesariamente una subsecuencia real completa; conserva el menor final posible para cada longitud.
En cuadrículas, el estado suele ser una celda y la transición depende de direcciones permitidas.
Ejemplo de caminos desde arriba e izquierda:
dp[row][col] = dp[row - 1][col] + dp[row][col - 1]Define primero:
Si hay ciclos en el grafo de estados, una tabulación simple por filas puede no ser válida.
El estado representa un rango:
dp[left][right]Aparece cuando una decisión divide un intervalo o cuando el orden de combinar elementos importa. Se llena normalmente por longitud creciente para garantizar que los subintervalos ya estén resueltos.
Cada nodo devuelve información de su subárbol. El estado puede incluir si el nodo se toma, su contribución o varias posibilidades.
La estructura del árbol elimina ciclos si se conserva el padre o se recorre desde una raíz.
Cuando el estado incluye un subconjunto pequeño, un bitmask puede representarlo:
mask = 010101₂El bit i indica si el elemento i está usado. Esto produce hasta 2^n estados, por lo que solo es práctico para n pequeño, normalmente alrededor de 20 o menos según la transición y los límites reales.
Guardar solo el mejor valor no siempre basta. Para recuperar decisiones, conserva:
parent o decisión elegida;La optimización de memoria puede impedir reconstruir el camino. Ese es un trade-off, no un error.
| Técnica | Qué explora | Qué reutiliza o descarta |
|---|---|---|
| Backtracking | Árbol de decisiones | Poda ramas imposibles |
| DP | Estados | Reutiliza estados equivalentes |
| Greedy | Una secuencia de elecciones | Descarta alternativas mediante una prueba |
Un backtracking puede convertirse en DP cuando distintos caminos llegan al mismo estado y el futuro depende solo de ese estado.
dp[...] en una frase.¿Por qué en knapsack 0/1 la versión 1D recorre la capacidad de mayor a menor?
Para que dp[capacity - weight] todavía represente la fila anterior, donde el objeto actual no se había usado. Si se recorre de menor a mayor, el valor ya actualizado puede reutilizar el mismo objeto varias veces.