Programación dinámica desde la recursión

Fibonacci recursivo con $n=50$ tarda una eternidad, y no porque el problema sea difícil: es porque calcula el mismo valor millones de veces. Guardar cada resultado la primera vez lo baja a instantáneo. Eso es toda la programación dinámica, y el resto es saber qué hay que guardar.

Las dos condiciones que la habilitan

Sirve cuando se cumplen dos condiciones. Subestructura óptima: la solución óptima se arma con soluciones óptimas de subproblemas. Y subproblemas superpuestos: los mismos subproblemas aparecen una y otra vez.

La segunda es la que la distingue de divide y vencerás. Mergesort parte en mitades que nunca se repiten, así que memorizar no ahorraría nada. Acá el árbol de recursión se pisa consigo mismo, y ese solapamiento es exactamente lo que se cobra.

Definir el estado es el único paso difícil

El paso difícil, y el único que importa, es definir el estado: qué parámetros identifican un subproblema sin ambigüedad. Escrito el estado, la recurrencia suele salir sola y el código es mecánico.

Un estado incompleto da resultados incorrectos porque dos situaciones distintas comparten entrada. Un estado con parámetros de más multiplica el costo sin necesidad. La pregunta que guía es: ¿qué necesito saber del pasado para decidir de acá en adelante?

Memoización o tabla, de abajo hacia arriba

Hay dos formas de escribirlo. De arriba hacia abajo: la recursión natural más una tabla que guarda cada resultado la primera vez que se calcula (memorización). De abajo hacia arriba: un ciclo que llena la tabla en un orden que garantiza tener listas las dependencias.

Dan lo mismo. La memorización es más fácil de derivar desde la recursión y sólo calcula los estados que hace falta; la iterativa no usa pila y suele tener mejores constantes. Conviene escribir primero la recursiva y convertirla si molesta.

Estados por costo de cada uno

El costo se estima con una cuenta simple: cantidad de estados por costo de resolver cada uno. En la mochila 0/1 los estados son objeto y capacidad restante, y cada uno decide entre tomar o no tomar: $O(n\,W)$.

Ojo con leer eso como “polinomial”. $W$ es un número, no el tamaño de la entrada: escrito con sus dígitos, el costo es exponencial en la cantidad de bits. Se lo llama pseudopolinomial, y es la razón por la que la mochila sigue siendo NP-difícil aunque tenga esta solución.

La memoria suele ser el límite

La memoria suele ser el límite antes que el tiempo. Muchas recurrencias sólo miran la fila anterior de la tabla, y entonces alcanza con guardar dos filas —o una sola, recorriéndola en el sentido correcto—.

Eso baja el espacio de $O(n\,W)$ a $O(W)$ y es la optimización más común. Lo que se pierde es la reconstrucción de la solución: con la tabla completa se puede rastrear qué decisiones la formaron; con una fila, sólo queda el valor óptimo.

La familia es reconocible

La familia es reconocible. Subsecuencia común más larga y distancia de edición: el estado son dos prefijos. Corte de varillas y cambio de monedas: el estado es la cantidad restante. Caminos en una grilla: el estado es la celda.

También aparece sobre grafos sin ciclos, donde Bellman-Ford y Floyd-Warshall son programación dinámica declarada. El indicio para sospecharla es un problema de optimización con decisiones secuenciales y un “elijo esto o aquello” en cada paso.

De la recursión a la tabla

El camino que conviene seguir siempre es el mismo: escribir la recursión ingenua, memorizarla, y recién después —si hace falta— darla vuelta en una tabla.

// 1. La recursión: correcta, y exponencial por recalcular
const knapsack = (weights: number[], values: number[], index: number, left: number): number => {
  if (index === weights.length || left === 0) return 0;
  if (weights[index]! > left) return knapsack(weights, values, index + 1, left);

  return Math.max(
    knapsack(weights, values, index + 1, left),                              // sin este
    values[index]! + knapsack(weights, values, index + 1, left - weights[index]!), // con este
  );
};

Memorizar es agregar un diccionario y dos líneas. Lo importante es que la clave del diccionario sea exactamente el estado del que depende el resultado:

const memoized = (weights: number[], values: number[]): number => {
  const seen = new Map<string, number>();

  const solve = (index: number, left: number): number => {
    if (index === weights.length || left === 0) return 0;

    const key = `${index}:${left}`;
    const cached = seen.get(key);
    if (cached !== undefined) return cached;

    const best = weights[index]! > left
      ? solve(index + 1, left)
      : Math.max(solve(index + 1, left), values[index]! + solve(index + 1, left - weights[index]!));

    seen.set(key, best);
    return best;
  };

  return solve(0, weights[weights.length - 1] ?? 0);
};

La versión con tabla recorre los mismos estados en orden, sin recursión y sin diccionario, y es la que se ve en los libros. Se llega a ella dando vuelta la memorizada, no escribiéndola de cero.

Cuándo es dinámica y cuándo es otra cosa

Las dos condiciones que hay que verificar antes de empezar son subproblemas superpuestos —el mismo estado aparece muchas veces en el árbol de recursión— y subestructura óptima —la solución óptima del problema contiene soluciones óptimas de sus subproblemas—. La primera se detecta dibujando dos niveles del árbol y viendo si algo se repite. La segunda es la que se saltea y la que da mal.

Cierre

Programación dinámica es recursión que no repite trabajo. Se define el estado, se escribe la recurrencia, se memoriza o se itera, y se estima el costo como estados por trabajo. La parte creativa es el estado; lo demás es traducción.