Programación Dinámica es una técnica de diseño algorítmico que toma un problema definido recursivamente, detecta que algunos subproblemas se repiten y evita resolverlos más de una vez guardando sus respuestas.

El intercambio principal es claro: PD suele reducir tiempo, pero aumenta espacio. Ese espacio aparece en tablas, diccionarios, matrices o vectores que almacenan resultados parciales.

Antes de diseñar una solución con Programación Dinámica, hay que comprobar que el problema realmente tiene estructura compatible. Si no cumple estos requisitos, usar PD será una decoración costosa, no una técnica correcta.

Una solución de Programación Dinámica no es solo una fórmula. En problemas de optimización, normalmente se necesitan estructuras para guardar valores, decisiones y reconstruir la solución final.

El error típico es empezar por la tabla. Eso está al revés. En Programación Dinámica primero se modela el problema recursivamente; después, con base en ese modelo, se diseña la tabla o la memoización.

Una vez existe el modelo recursivo, la Programación Dinámica consiste en convertir ese modelo en una estructura de almacenamiento y un orden de cálculo.

Factorial es un ejemplo guía útil porque su modelo recursivo es simple. Pero hay que decir la verdad: no es un gran caso de PD, porque no tiene subproblemas repetidos. Sirve para entender la mecánica de pasar de recursión a tabla, no para presumir una mejora algorítmica.

factorial(n) BEGIN
  IF (n = 0 OR n = 1) THEN BEGIN
    RETURN 1;
  END
  RETURN n * factorial(n - 1);
END

factorialTD(n, Tabla[n]) BEGIN
  IF (n = 0 OR n = 1) THEN BEGIN
    RETURN 1;
  END
  IF (Tabla[n] != -1) THEN BEGIN
    RETURN Tabla[n];
  END
  Tabla[n] <- n * factorialTD(n - 1, Tabla);
  RETURN Tabla[n];
END

factorialBU(n) BEGIN
  Tabla[0] <- 1;
  Tabla[1] <- 1;
  FOR i <- 2 TO n DO BEGIN
    Tabla[i] <- Tabla[i - 1] * i;
  END
  RETURN Tabla[n];
END

Fibonacci es el ejemplo canónico de Programación Dinámica porque la recursión ingenua recalcula los mismos subproblemas muchas veces. Aquí sí hay una mejora real: se pasa de crecimiento exponencial a crecimiento lineal.

En este modelo, $n$ es el parámetro de estado que representa el índice del número de Fibonacci que queremos calcular. Los casos base $n=0$ y $n=1$ detienen la recursión, mientras que la transición suma los dos subproblemas inmediatamente anteriores.

Cada celda $dp[i]$ de la tabla almacena el valor óptimo ya calculado para el subproblema $i$. El uso de la tabla elimina la necesidad de volver a calcular el mismo valor múltiples veces.

En el enfoque Top-Down, la estructura sigue siendo recursiva, pero se intercala un paso de consulta a la memoria (memoización) antes de realizar cualquier llamado recursivo.

fibTD(n, Tabla[n]) BEGIN
  IF (n = 0 OR n = 1) THEN BEGIN
    RETURN n;
  END
  IF (Tabla[n] != -1) THEN BEGIN
    RETURN Tabla[n];
  END
  Tabla[n] <- fibTD(n - 1, Tabla) + fibTD(n - 2, Tabla);
  RETURN Tabla[n];
END

fibBU(n) BEGIN
  Tabla[0] <- 0;
  Tabla[1] <- 1;
  FOR i <- 2 TO n DO BEGIN
    Tabla[i] <- Tabla[i - 1] + Tabla[i - 2];
  END
  RETURN Tabla[n];
END

fibBUOptimizado(n) BEGIN
  IF (n = 0 OR n = 1) THEN BEGIN
    RETURN n;
  END
  anterior2 <- 0;
  anterior1 <- 1;
  FOR i <- 2 TO n DO BEGIN
    actual <- anterior1 + anterior2;
    anterior2 <- anterior1;
    anterior1 <- actual;
  END
  RETURN actual;
END

Top-Down y Bottom-Up resuelven el mismo modelo de Programación Dinámica, pero recorren los estados de forma distinta. Top-Down conserva la recursión y calcula bajo demanda. Bottom-Up elimina la recursión y llena la tabla en un orden explícito.

Dadas dos cadenas $X$ de longitud $m$ y $Y$ de longitud $n$, el problema LCS busca la longitud de la subsecuencia más larga que aparece en ambas cadenas.

Como en cualquier problema de PD, primero se modela recursivamente. En LCS se comparan los últimos caracteres de los prefijos $X[\mathrm{1..}i]$ y $Y[\mathrm{1..}j]$.

Aquí, los parámetros $i$ y $j$ indican los prefijos de las cadenas $X$ e $Y$. La condición $X[i]=Y[j]$ suma 1 al óptimo anterior porque hemos encontrado un carácter común. Si no coinciden, usamos $\max$ para elegir la mejor decisión entre avanzar en una cadena u otra.

Después de escribir el modelo recursivo, cada estado $LCS(i,j)$ se convierte en una celda $dp[i][j]$.

La celda $dp[i][j]$ de la tabla almacena la longitud de la LCS calculada hasta los prefijos actuales. Al igual que en el modelo recursivo, si hay un fallo de coincidencia, la función $\max$ nos permite conservar el mejor valor alcanzado en los estados vecinos.

La inicialización viene directamente del caso base: si un prefijo tiene longitud cero, la LCS mide cero.

LCS(X[m], Y[n]) BEGIN
 FOR i <- 0 TO m DO BEGIN
 dp[i][0] <- 0;
 END
 FOR j <- 0 TO n DO BEGIN
 dp[0][j] <- 0;
 END

 FOR i <- 1 TO m DO BEGIN
 FOR j <- 1 TO n DO BEGIN
 IF (X[i] = Y[j]) THEN BEGIN
 dp[i][j] <- dp[i - 1][j - 1] + 1;
 path[i][j] <- "diagonal";
 END
 ELSE BEGIN
 IF (dp[i - 1][j] >= dp[i][j - 1]) THEN BEGIN
 dp[i][j] <- dp[i - 1][j];
 path[i][j] <- "arriba";
 END
 ELSE BEGIN
 dp[i][j] <- dp[i][j - 1];
 path[i][j] <- "izquierda";
 END
 END
 END
 END

 RETURN dp[m][n];
END

La tabla de óptimos no es una tabla decorativa: cada celda tiene significado. $dp[i][j]$ responde cuál es la longitud de la LCS entre los primeros $i$ caracteres de $X$ y los primeros $j$ caracteres de $Y$

El recorrido hacia atrás empieza en $dp[m][n]$. Desde ahí se siguen las decisiones hasta llegar a la primera fila o primera columna.

reconstruirLCS(X[m], Y[n], dp[m][n]) BEGIN
 i <- m;
 j <- n;
 solucion <- "";

 WHILE (i > 0 AND j > 0) DO BEGIN
 IF (X[i] = Y[j]) THEN BEGIN
 solucion <- X[i] + solucion;
 i <- i - 1;
 j <- j - 1;
 END
 ELSE BEGIN
 IF (dp[i - 1][j] >= dp[i][j - 1]) THEN BEGIN
 i <- i - 1;
 END
 ELSE BEGIN
 j <- j - 1;
 END
 END
 END

 RETURN solucion;
END

La versión Top-Down copia casi literalmente el modelo recursivo. La única diferencia es que antes de resolver un estado revisa si ya está guardado.

El modelo Top-Down mantiene la estructura recursiva original, pero utiliza una tabla de memoización para almacenar y reutilizar los resultados de los subproblemas $(i,j)$ ya resueltos, evitando así el costo exponencial de los cálculos repetidos.

LCSTD(X[m], Y[n], i, j, memo[m][n]) BEGIN
 IF (i = 0 OR j = 0) THEN BEGIN
 RETURN 0;
 END

 IF (memo[i][j] != -1) THEN BEGIN
 RETURN memo[i][j];
 END

 IF (X[i] = Y[j]) THEN BEGIN
 memo[i][j] <- 1 + LCSTD(X, Y, i - 1, j - 1, memo);
 END
 ELSE BEGIN
 a <- LCSTD(X, Y, i - 1, j, memo);
 b <- LCSTD(X, Y, i, j - 1, memo);
 memo[i][j] <- max(a, b);
 END

 RETURN memo[i][j];
END

La dimensión de la tabla no se decide al azar. Sale directamente del estado. Un estado con un parámetro suele producir una tabla 1D; un estado con dos parámetros suele producir una tabla 2D.

Muchas tablas de PD parecen necesitar toda la matriz, pero para calcular el valor final a veces basta conservar una parte pequeña. La regla es mirar las dependencias de cada celda.