¿Qué es la programación dinámica?
Paso 1 de 10
Merge sort (ordenamiento por mezcla) sobre [5, 2, 9, 1]: parte por la mitad dos veces hasta que cada pieza sea un valor.
La idea
La programación dinámica aplica cuando se cumplen dos cosas: el mismo subproblema reaparece una y otra vez, y la mejor respuesta total se arma con las mejores subrespuestas. Merge sort (ordenamiento por mezcla) parte en mitades nuevas que nunca se superponen, así que guardar en caché no aporta nada. Las ramas de Fibonacci chocan todo el tiempo, así que la caché lo aporta todo. Ya lo hiciste a mano en Memoización: la DP es ese hábito, hecho a propósito.
Ejemplo del mundo real
Una pastelería calcula el costo de su menú de pasteles. La mitad de las recetas usa la misma crema de mantequilla, así que el pastelero calcula el precio de una tanda una sola vez y pega la cifra en la pared. Cada pastel que la usa lee ese número en lugar de volver a costear mantequilla, azúcar y mano de obra desde cero.
El código
Te toca
¿Qué imprime esto?
from functools import lru_cache
@lru_cache(maxsize=None)
def f(n):
return n if n < 2 else f(n - 1) + f(n - 2)
f(10)
print(f.cache_info().misses)Mini quiz
1 / 3