DP: Coin Change y LCS

Coin Change (cambio de monedas) es el "Hello World" de la Programación Dinámica: dado un monto y denominaciones de monedas, ¿cuántas monedas mínimas necesitas? La clave de DP es identificar el subproblema: dp[amount] = mínimas monedas para ese monto. Para cada monto de 1 a target, considera cada moneda: dp[amount] = min(dp[amount], dp[amount - coin] + 1). La tabla dp se construye de abajo hacia arriba y el resultado final es dp[target].

Longest Common Subsequence (LCS) es el prototipo de DP 2D: dadas dos strings, encontrar la subsecuencia común más larga. La tabla dp[i][j] = longitud de la LCS de los primeros i caracteres del string A y los primeros j del string B. Si los caracteres coinciden, dp[i][j] = dp[i-1][j-1] + 1. Si no, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Esta tabla 2D de "decisiones" es el patrón de LCS, Edit Distance, y muchos otros problemas de strings.

// COIN CHANGE - mínimo de monedas para una cantidad
// dp[i] = mínimo de monedas para cantidad i
function coinChange(monedas, cantidad) {
  const dp = new Array(cantidad + 1).fill(Infinity);
  dp[0] = 0; // Base: 0 monedas para cantidad 0
  
  for (let i = 1; i <= cantidad; i++) {
    for (const moneda of monedas) {
      if (moneda <= i && dp[i - moneda] + 1 < dp[i]) {
        dp[i] = dp[i - moneda] + 1;
      }
    }
  }
  
  return dp[cantidad] === Infinity ? -1 : dp[cantidad];
}

console.log(coinChange([1, 5, 10, 25], 41)); // 4 monedas: 25+10+5+1
console.log(coinChange([2], 3));             // -1 (imposible)

// LONGEST COMMON SUBSEQUENCE
// ¿Cuál es la subsecuencia más larga que comparten dos strings?
function lcs(s1, s2) {
  const m = s1.length, n = s2.length;
  // dp[i][j] = LCS de s1[0..i] y s2[0..j]
  const dp = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(0)
  );
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i-1] === s2[j-1]) {
        dp[i][j] = dp[i-1][j-1] + 1; // Caracteres iguales
      } else {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // Toma el mayor
      }
    }
  }
  
  return dp[m][n];
}

console.log(lcs("ABCBDAB", "BDCABA")); // 4 ("BCBA" o "BDAB")

// APLICACIÓN: Mínimo de ediciones (Edit Distance / Levenshtein)
function editDistance(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m+1 }, (_, i) =>
    Array.from({ length: n+1 }, (_, j) => i || j)
  );
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = s1[i-1] === s2[j-1]
        ? dp[i-1][j-1]
        : 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
    }
  }
  return dp[m][n];
}

console.log(editDistance("kitten", "sitting")); // 3