Data Structure & Algorithms
Fundamentos de dynamic programming: diseño de estado, transición, casos base, memoization, tabulación, orden de cálculo y memoria.
Dynamic programming resuelve problemas con subproblemas repetidos guardando sus resultados. La parte difícil no es usar un array llamado dp; es definir un estado que contenga toda la información necesaria para decidir el futuro, sin conservar historia irrelevante.
Busca dos propiedades:
Recursión por sí sola no implica DP. Si cada subproblema aparece una sola vez, memoizar puede añadir memoria sin evitar trabajo.
Completa esta frase:
dp[state]representa...
Ejemplo para subir escaleras:
dp[i] = cantidad de formas de llegar exactamente al escalón iUn buen estado cumple el principio de Markov algorítmico: una vez conocido, el futuro no necesita saber el camino completo usado para llegar.
Pregunta cuál pudo ser la última decisión.
Si se puede llegar al escalón i desde i - 1 o i - 2:
dp[i] = dp[i - 1] + dp[i - 2]La transición no se memoriza; se deriva de las formas válidas de entrar al estado.
Los casos base representan los estados mínimos que ya conoces.
dp[0] = 1En problemas de conteo, “hacer nada” puede ser una forma válida. Elegir 0 o 1 sin interpretar el estado produce errores silenciosos.
Parte de una función recursiva y guarda cada estado.
function climbStairs(steps: number): number {
if (steps < 0) return 0;
const memo = new Map<number, number>();
function count(remaining: number): number {
if (remaining === 0) return 1;
if (remaining < 0) return 0;
const cached = memo.get(remaining);
if (cached !== undefined) return cached;
const result = count(remaining - 1) + count(remaining - 2);
memo.set(remaining, result);
return result;
}
return count(steps);
}Ventajas:
Costos:
Calcula estados en un orden donde sus dependencias ya existen.
function climbStairs(steps: number): number {
if (steps < 0) return 0;
if (steps <= 1) return 1;
const dp = Array(steps + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= steps; i += 1) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[steps];
}Tiempo: O(n), porque se calculan n + 1 estados con trabajo constante. Espacio: O(n) para la tabla.
Si la transición solo usa los dos estados anteriores, no necesitas toda la tabla.
function climbStairs(steps: number): number {
if (steps < 0) return 0;
if (steps <= 1) return 1;
let previousTwo = 1;
let previousOne = 1;
for (let i = 2; i <= steps; i += 1) {
const current = previousOne + previousTwo;
previousTwo = previousOne;
previousOne = current;
}
return previousOne;
}Espacio adicional: O(1). Haz esta optimización después de comprender las dependencias; no antes.
Toda DP puede verse como un grafo dirigido:
Si hay ciclos sin una medida que disminuya o sin un tratamiento especial, la recurrencia puede no terminar.
tiempo = número de estados × trabajo por estado
espacio = estados almacenados + call stack + estructuras auxiliaresEjemplo: n × capacity estados y dos decisiones constantes producen O(n × capacity).
Ese tiempo puede ser pseudo-polinomial: depende del valor numérico de capacity, no solo del número de bits usados para representarlo.
Memoizar cualquier función no garantiza una buena solución. Las claves deben representar estados equivalentes. Si incluyes objetos completos o decisiones pasadas innecesarias, puedes impedir que dos caminos reutilicen el mismo resultado.
estado → qué necesito saber
transición → cómo llego desde estados menores
caso base → qué sé sin resolver más
orden → cuándo están disponibles las dependencias
resultado → en qué estado está la respuesta¿Qué diferencia conceptual hay entre un parámetro recursivo y una dimensión necesaria del estado?
Un parámetro solo debe formar parte de la clave de DP si puede cambiar el conjunto de decisiones o resultados futuros. Algunos parámetros sirven para construir la respuesta o registrar el camino, pero no cambian el subproblema y no deberían distinguir estados.