Dynamic Programming

La programación dinámica (DP) resuelve problemas que parecen exponencialmente difíciles guardando los resultados de subproblemas para no recalcularlos. Imagina la secuencia de Fibonacci: calcular fib(40) de forma recursiva realiza millones de llamadas repetidas, pero si guardas cada resultado en un arreglo, son solo 40 operaciones. El nombre "dinámica" no describe la técnica —fue elegido por su inventor para impresionar a un comité militar en los años 50.

DP se aplica cuando el problema tiene dos propiedades: subproblemas solapados (los mismos subproblemas se calculan múltiples veces) y subestructura óptima (la solución óptima del problema grande se construye desde soluciones óptimas de los subproblemas). Hay dos enfoques: top-down con memoización (recursión + caché) y bottom-up con tabulación (llenar una tabla desde los casos base).

Los problemas clásicos son Fibonacci, escaleras de Hogwarts, la mochila (knapsack), Coin Change, y la Longest Common Subsequence.

// Patrón DP: identificar subproblemas solapados

// Problema: Fibonacci
// Top-down (memoización)
function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibMemo(n-1, memo) + fibMemo(n-2, memo);
  memo.set(n, result);
  return result;
}

// Bottom-up (tabulación)
function fibTabla(n) {
  if (n <= 1) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}

// Problema clásico: Subida de escaleras
// Cuántas formas de subir n escalones (1 o 2 a la vez)
function escaleras(n) {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const actual = prev1 + prev2;
    prev2 = prev1;
    prev1 = actual;
  }
  return prev1;
}

// Problema: Mochila 0/1
function mochila(pesos, valores, capacidad) {
  const n = pesos.length;
  const dp = Array.from({ length: n+1 },
    () => new Array(capacidad+1).fill(0));
  
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacidad; w++) {
      if (pesos[i-1] <= w) {
        dp[i][w] = Math.max(
          dp[i-1][w], // Sin este objeto
          dp[i-1][w - pesos[i-1]] + valores[i-1] // Con este objeto
        );
      } else {
        dp[i][w] = dp[i-1][w];
      }
    }
  }
  return dp[n][capacidad];
}