Saltar al contenido

¿Qué es la programación dinámica?

Lección 1 de 20 · 5 min

¿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

¿Qué par de propiedades convierte un problema en un problema de DP?