Ir al contenido
wannacode

Subproblemas superpuestos

En resumen: La programación dinámica resuelve cada subproblema una vez y guarda la respuesta: con memoización de arriba abajo o con una tabla de abajo hacia arriba, en lugar de una recursión que resuelve lo mismo una y otra vez.

Problema

El plan de carga

Un mensajero va en un scooter eléctrico por una ruta de n km. Hay una estación de carga en cada kilómetro, y la batería dura como máximo 2 km. Así que desde cada parada el mensajero avanza 1 o 2 km hasta la siguiente. En cada estación donde se detiene, paga su tarifa. Las tarifas son distintas, y la aplicación tiene que encontrar el plan más barato.

La primera solución piensa hacia atrás. La última parada es el km n. Antes, el mensajero estaba en el km n − 1 o en el km n − 2. Así que lo más barato hasta n es la tarifa en n más lo más barato de los dos: lo más barato hasta n − 1 y lo más barato hasta n − 2. Eso es recursión, como en la lección «Recursión». Las tarifas están en céntimos, y el contador dice cuántas veces se llamó a la función:

static long calls = 0;


static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}


static int cheapest(int[] fee, int i) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    int oneBack = cheapest(fee, i - 1);
    int twoBack = cheapest(fee, i - 2);
    return fee[i] + Math.min(oneBack, twoBack);
}


for (int km : new int[] {10, 30}) {
    calls = 0;
    int cost = cheapest(fees(km), km);
    System.out.println(km + " km: " + cost + " céntimos, " + calls + " llamadas");
}
Salida
10 km: 381 céntimos, 177 llamadas
30 km: 1217 céntimos, 2692537 llamadas

La respuesta es correcta, pero para 30 km se llamó a la función 2 692 537 veces. Para 50 km se llamaría 40 730 022 147 veces: a mil millones de llamadas por segundo es más de medio minuto, y una ruta de mensajero puede tener 100 km.

La idea

La misma pregunta, hecha millones de veces

¿Por qué tantas? Sigue quién pregunta qué. Lo más barato hasta el km 30 pregunta por el km 29 y el km 28. El km 29 pregunta por 28 y 27. El km 28 se pregunta dos veces, y cada vez se calcula desde cero, junto con todo lo que hay debajo. Más abajo las repeticiones se acumulan: el km 27 se pregunta tres veces, el km 26 cinco veces.

El ejemplo limpio de esto son los números de Fibonacci: cada uno es la suma de los dos anteriores, 0, 1, 1, 2, 3, 5, 8… La función tiene la misma forma, los dos más pequeños y una suma:

static long fib(int n) {
    calls++;
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}
Salida
fib(30) = 832040, 2692537 llamadas

El número de llamadas es el mismo hasta la última cifra, porque el árbol de llamadas es el mismo. Y el plan es solo uno de muchos lugares con este árbol.

Estos subproblemas se llaman superpuestos: el mismo problema más pequeño lo necesitan varios más grandes. En divide y vencerás no es así. El ordenamiento por mezcla parte los pedidos en dos mitades que no comparten ni un solo pedido, y cada trozo se resuelve una vez. Aquí «lo más barato hasta el km 28» lo necesitan el km 29 y el km 30.

Míralo

El árbol y la memoria

Todo el árbol de llamadas para 6 km, y luego lo mismo con memoria. Fíjate en qué cajas se repiten y qué les pasa en cuanto se recuerda su respuesta:

static int cheapestMemo(int[] fee, int i, int[] memo) {
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}
Paso a paso, en palabras
  1. Cada caja es una llamada cheapest(k): lo más barato hasta el km k. cheapest(6) pregunta por 5 y 4, y cada uno de ellos pregunta por otros dos más pequeños.
  2. El árbol se detiene en el km 1 y 0, donde la respuesta es la propia tarifa. Para 6 km son 25 llamadas.
  3. Las mismas preguntas una y otra vez: cheapest(4) dos veces, cheapest(3) tres veces, cheapest(2) cinco veces. Los subproblemas se superponen.
  4. Con memoria: las llamadas van en el mismo orden, y la primera vez que se calcula una respuesta entra en memo, abajo.
  5. La segunda vez la respuesta ya está en memo (verde): todo el subárbol de debajo ni siquiera se ejecuta. 11 llamadas en lugar de 25.
  6. Una tabla de abajo hacia arriba: best[0] y best[1] son las tarifas, y cada celda siguiente se construye con las dos anteriores. 5 celdas, sin recursión.
  7. Cada celda necesita solo las dos últimas. Dos variables avanzan deslizándose en lugar de la tabla: O(n) de tiempo y O(1) de memoria.

La idea

Recordar la respuesta

La solución es no calcular lo mismo dos veces. La primera vez que calculas lo más barato hasta el km k, anótalo. La próxima vez que alguien pregunte por k, devuelve lo que anotaste.

static long calls = 0;


static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}


static int cheapestMemo(int[] fee, int i, int[] memo) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}


int[] fee = fees(30);
int[] memo = new int[fee.length];
Arrays.fill(memo, -1);
int cost = cheapestMemo(fee, 30, memo);
System.out.println(cost + " céntimos, " + calls + " llamadas");
Salida
1217 céntimos, 59 llamadas
La memoria es un arreglo con un lugar para cada kilómetro. -1 significa «todavía no calculado»: las tarifas son positivas, así que una respuesta real nunca es -1.

Esto se llama memoización (recordar los resultados). La función es la misma recursión, solo que con memoria. 59 llamadas en lugar de 2 692 537: cada kilómetro se calcula una vez, y la segunda pregunta sobre él devuelve la respuesta ya hecha.

Un problema que se construye con las respuestas de problemas más pequeños, cuando esos más pequeños se repiten, se resuelve con programación dinámica: cada subproblema se resuelve una vez y se guarda su respuesta. El nombre es antiguo y no dice mucho. Recuérdalo como «recordar y reutilizar».

Pruébalo

Predice la salida

La misma función con memoria, para una ruta de 8 km. ¿Cuántas veces se llamará?

static long calls = 0;


static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}


static int cheapestMemo(int[] fee, int i, int[] memo) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}


int[] fee = fees(8);
int[] memo = new int[fee.length];
Arrays.fill(memo, -1);
int cost = cheapestMemo(fee, 8, memo);
System.out.println(cost + " céntimos, " + calls + " llamadas");
Respuesta

La idea

De abajo hacia arriba

La recursión con memoria empieza en el km n y baja hasta llegar a los pequeños. También puedes ir al revés: empezar por los pequeños y subir. Lo más barato hasta el km 0 y el km 1 es la propia tarifa. De ahí sale el km 2, luego el km 3, y así hasta n. Cuando llegas a una celda, las dos de debajo ya están hechas.

static int cheapestTable(int[] fee) {
    int n = fee.length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++) {
        int cheaper = Math.min(best[i - 1], best[i - 2]);
        best[i] = fee[i] + cheaper;
    }
    return best[n];
}

Esto es programación dinámica de abajo hacia arriba, con una tabla. No hay recursión ni comprobación de «¿ya está calculado?»: el orden del bucle garantiza que todo lo necesario ya está en la tabla. Hay n − 1 celdas, con un trozo de trabajo por celda: O(n).

Una observación más. La celda i solo mira i − 1 e i − 2. Todo lo anterior ya no hace falta. Así que toda la tabla puede convertirse en dos variables que avanzan deslizándose:

static int cheapestPair(int[] fee) {
    int twoBack = fee[0];
    int oneBack = fee[1];
    for (int i = 2; i < fee.length; i++) {
        int here = fee[i] + Math.min(oneBack, twoBack);
        twoBack = oneBack;
        oneBack = here;
    }
    return oneBack;
}
int[] fee = fees(30);
System.out.println("tabla: " + cheapestTable(fee) + " céntimos");
System.out.println("dos variables: " + cheapestPair(fee) + " céntimos");
Salida
tabla: 1217 céntimos
dos variables: 1217 céntimos

El tiempo sigue siendo O(n), y la memoria O(1): dos números, por larga que sea la ruta.

Míralo

Mídelo: sin memoria, con memoria, con tabla

Ejecuta las tres en rutas de 10, 20 y 30 km. Contamos las llamadas de la función y, en la tabla, las celdas. La recursión sin memoria no se ejecuta por encima de 30 km: con 40 km son 331 160 281 llamadas y la página se congelaría.

  • Recursión sin memoria O(2ⁿ)
  • Recursión con memoria O(n)
  • Tabla, de abajo hacia arriba O(n)
Algoritmon = 10n = 20n = 30
Recursión sin memoria17721.8912.692.537
Recursión con memoria193959
Tabla, de abajo hacia arriba91929
El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.
static int cheapestMemo(int[] fee, int i, int[] memo) {
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}

Cada 10 km la recursión sin memoria se multiplica por unas 123, mientras que las otras dos crecen en 20 y en 10. La curva de Bench lleva la etiqueta O(2ⁿ): es exponencial, con una base de aproximadamente 1,6, la razón entre dos números de Fibonacci vecinos.

Más precisamente, para curiosos

Los mismos números en tu lenguaje: las llamadas sin memoria, con memoria y las celdas de la tabla para 10, 20 y 30 km.

static long calls = 0;
static long cells = 0;


static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}


static int cheapest(int[] fee, int i) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    int oneBack = cheapest(fee, i - 1);
    int twoBack = cheapest(fee, i - 2);
    return fee[i] + Math.min(oneBack, twoBack);
}


static int cheapestMemo(int[] fee, int i, int[] memo) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}


static int cheapestTable(int[] fee) {
    int n = fee.length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++) {
        cells++;
        int cheaper = Math.min(best[i - 1], best[i - 2]);
        best[i] = fee[i] + cheaper;
    }
    return best[n];
}


for (int km : new int[] {10, 20, 30}) {
    int[] fee = fees(km);
    calls = 0;
    cheapest(fee, km);
    long plain = calls;
    calls = 0;
    int[] memo = new int[fee.length];
    Arrays.fill(memo, -1);
    cheapestMemo(fee, km, memo);
    cells = 0;
    int cost = cheapestTable(fee);
    System.out.println(km + " km: " + plain + " / " + calls + " / " + cells + ", " + cost + " céntimos");
}
Salida
10 km: 177 / 19 / 9, 381 céntimos
20 km: 21891 / 39 / 19, 822 céntimos
30 km: 2692537 / 59 / 29, 1217 céntimos

Pruébalo

Encuentra el error

Un compañero escribió la función con memoria. La respuesta es correcta, pero el contador muestra lo mismo que sin memoria:

int[] fee = fees(30);
int[] memo = new int[fee.length];
Arrays.fill(memo, -1);
int cost = cheapestMemo(fee, 30, memo);
System.out.println(cost + " céntimos, " + calls + " llamadas");
Salida
1217 céntimos, 2692537 llamadas

¿Qué línea tiene el error?

Elige la línea con el error.

Pruébalo

Completa

La celda i de la tabla es la tarifa en el km i más lo más barato de los dos lugares de los que puedes venir. ¿Cuál es el segundo?

static int cheapestTable(int[] fee) {
    int n = fee.length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++) {
        int cheaper = Math.min(best[i - 1], );
        best[i] = fee[i] + cheaper;
    }
    return best[n];
}

Ejercicio

Las tarifas de la entrada

Resuélvelo en tu editor.

El plan más barato. Lee las tarifas de las estaciones del km 1 al km n (en céntimos, separadas por espacios) e imprime el plan más barato. Usa cheapestPair de la lección.

Entrada
77 114 61 98 45 82
Salida
Lo más barato: 265 céntimos

Más tareas

  • Qué estaciones. Imprime también los kilómetros donde se detiene el mensajero. Pista: junto a la tabla, guarda de dónde vino cada celda (i − 1 o i − 2), y vuelve atrás desde n.
  • Cuántos planes. Cuenta todos los planes, sin importar lo que cuesten. ¿Cuántos hay para 30 km? Compara los números con los de Fibonacci. (Para 30 km hay 1 346 269.)
  • Una batería mejor. El scooter nuevo dura 3 km. ¿Cómo cambia la fórmula y cuántas variables necesitas en lugar de dos?

Más precisamente

La profundidad y la memoria integrada

La memoria recorta el trabajo, pero la recursión sigue siendo recursión.

Más precisamente, para curiosos

Hasta dónde baja. La recursión con memoria baja primero por la cadena n, n − 1, … 1, y solo entonces empieza a guardar. La pila de llamadas tiene n marcos, como en la lección «La pila de llamadas por dentro». La tabla hace el mismo trabajo en un bucle, y la pila no crece, como en «De la recursión al bucle».

static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}


static int cheapestMemo(int[] fee, int i, int[] memo) {
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}


static int cheapestTable(int[] fee) {
    int n = fee.length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++) {
        int cheaper = Math.min(best[i - 1], best[i - 2]);
        best[i] = fee[i] + cheaper;
    }
    return best[n];
}


int[] fee = fees(1000000);
try {
    int[] memo = new int[fee.length];
    Arrays.fill(memo, -1);
    cheapestMemo(fee, 1000000, memo);
} catch (StackOverflowError e) {
    System.out.println("cheapestMemo: StackOverflowError");
}
System.out.println("cheapestTable: " + cheapestTable(fee));
Salida
cheapestMemo: StackOverflowError
cheapestTable: 38866659
Java y JavaScript no tienen un límite en el número de niveles, pero la pila es de aproximadamente 1 MB, y 100 000 llamadas anidadas no caben. En Python el límite es de 1000 niveles.

Memoria integrada en el lenguaje. En Java es tentador escribir la memoria como memo.computeIfAbsent(i, k -> fee[k] + Math.min(...)) con la recursión dentro. No lo hagas con HashMap: una llamada recursiva que modifica el mismo mapa durante computeIfAbsent lanza ConcurrentModificationException (desde Java 9). Un arreglo, o containsKey + put, es seguro.

De arriba abajo o de abajo arriba. Los dos caminos resuelven los mismos subproblemas. Con memoria se calculan solo los que realmente se alcanzan, y se escribe directamente a partir de la recursión ingenua. Con una tabla no hay recursión y a menudo se puede reducir, como aquí. Si los subproblemas son muchos y la respuesta necesita pocos, gana la memoria. Si se necesitan casi todos, la tabla es más rápida y no arriesga la pila.

Test

Ponte a prueba

1. ¿Por qué la recursión sin memoria hace 2,7 millones de llamadas para 30 km, y con memoria solo 59?
2. ¿En qué se diferencia la programación dinámica de «divide y vencerás» en el ordenamiento por mezcla?
3. La tabla para n km se llena de best[2] a best[n]. ¿Cuánta memoria necesita la versión de dos variables?
4. Una función con memoria consulta la memoria pero nunca escribe en ella. ¿Qué pasa?
5. ¿Por qué la recursión con memoria falla en Python para 5000 km, mientras que la tabla funciona?

Creado por Ivo Gergov como parte de la campaña de Evo Tech por una educación accesible en programación ·