← Estructuras de datos desde cero · Lección 32/32
Programación dinámica: no calcular dos veces
El mismo trabajo, una y otra vez
¿De cuántas formas subes una escalera de n escalones si das pasos de 1 o de 2? Para llegar al escalón n vienes del n-1 o del n-2, así que formas(n) = formas(n-1) + formas(n-2).
La recursión directa es correcta pero terriblemente lenta: formas(n-2) se calcula dentro de formas(n-1) y otra vez afuera, y así hacia abajo. Las llamadas crecen como O(2ⁿ). Cuenta cuántas hace:
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
Con 25 escalones son 121 393 formas, pero casi 243 000 llamadas: cada resultado chico se recalcula miles de veces. Cada 5 escalones más, las llamadas se multiplican por 11.
Toda la lección en una página
El mismo trabajo, una y otra vez
¿De cuántas formas subes una escalera de n escalones si das pasos de 1 o de 2? Para llegar al escalón n vienes del n-1 o del n-2, así que formas(n) = formas(n-1) + formas(n-2).
La recursión directa es correcta pero terriblemente lenta: formas(n-2) se calcula dentro de formas(n-1) y otra vez afuera, y así hacia abajo. Las llamadas crecen como O(2ⁿ). Cuenta cuántas hace:
let llamadas = 0;
function formas(n) {
llamadas++;
if (n <= 1) return 1;
return formas(n - 1) + formas(n - 2);
}
for (const n of [10, 20, 25]) {
llamadas = 0;
const r = formas(n);
console.log(n, "escalones:", r, "formas,", llamadas, "llamadas");
}
Con 25 escalones son 121 393 formas, pero casi 243 000 llamadas: cada resultado chico se recalcula miles de veces. Cada 5 escalones más, las llamadas se multiplican por 11.
Memoizar: anotar antes de olvidar
La programación dinámica es resolver un problema con subproblemas que se repiten guardando cada respuesta la primera vez. La forma más directa es memoizar: antes de calcular, revisas si ya lo tienes en un Map; si no, lo calculas y lo anotas.
Ahora cada n se calcula una sola vez: O(n). Lo que sin memo habría tardado semanas sale al instante.
function formasMemo(n, memo = new Map()) {
if (n <= 1) return 1;
if (memo.has(n)) return memo.get(n);
const r = formasMemo(n - 1, memo) + formasMemo(n - 2, memo);
memo.set(n, r);
return r;
}
console.log(formasMemo(25));
console.log(formasMemo(70));
25 da lo mismo que antes, y 70 sale de inmediato: 308 061 521 170 129 formas. Sin memo, serían unos 600 billones de llamadas.
La tabla, de abajo hacia arriba
La otra forma es llenar una tabla desde el caso más chico hasta el que buscas, sin recursión. El reto de las monedas: ¿cuántas monedas, como mínimo, suman un monto?
dp[m] es el mínimo para el monto m. dp[0] = 0, y para cada m pruebas cada moneda c: dp[m - c] + 1. Con monedas de 1, 3 y 4 y un monto de 6, la respuesta es 2 (3 + 3). Tomar siempre la moneda más grande daría 4 + 1 + 1, tres monedas: por eso aquí no sirve el atajo «goloso» y hace falta la tabla.
La receta de siempre: estado (qué significa dp[m]), transición (cómo sale de los anteriores), caso base y orden de llenado.
function minMonedas(monedas, monto) {
const dp = new Array(monto + 1).fill(Infinity);
dp[0] = 0;
for (let m = 1; m <= monto; m++) {
for (const c of monedas) {
if (c <= m && dp[m - c] + 1 < dp[m]) dp[m] = dp[m - c] + 1;
}
}
console.log(dp);
return dp[monto] === Infinity ? -1 : dp[monto];
}
console.log(minMonedas([1, 3, 4], 6));
console.log(minMonedas([5, 10], 3));
- La tabla de
[1, 3, 4]es la del dibujo: el 6 se llena desde el 3 (dp[3] + 1 = 2). - Con monedas de 5 y 10 no hay forma de juntar 3: la tabla se queda en
Infinityy la función devuelve -1.
A veces la tabla cabe en dos variables
Si cada casilla sólo depende de la anterior, no hace falta guardar la tabla entera. El algoritmo de Kadane encuentra el subarreglo seguido con la suma más grande: en cada posición decides si sigues el tramo que traías o empiezas uno nuevo aquí, y recuerdas el mejor que has visto.
Es programación dinámica en O(n) de tiempo y O(1) de memoria.
function mayorSubarreglo(nums) {
let actual = nums[0], mejor = nums[0];
for (let i = 1; i < nums.length; i++) {
actual = Math.max(nums[i], actual + nums[i]);
mejor = Math.max(mejor, actual);
}
return mejor;
}
console.log(mayorSubarreglo([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(mayorSubarreglo([-3, -1, -2]));
- El 6 sale del tramo
[4, -1, 2, 1]: el -1 no alcanza a romperlo. - Si todo es negativo, el mejor tramo es el número menos malo, -1.