Memoización: almacenamiento en caché de resultados recursivos

El Fibonacci recursivo ingenuo calcula los mismos valores repetidamente. fib(5) llama a fib(4) y fib(3); fib(4) llama a fib(3) y fib(2), por lo que fib(3) se calcula dos veces. Esta redundancia crece de forma exponencial: fib(40) realiza más de mil millones de llamadas a funciones. La memoización resuelve este problema almacenando cada resultado la primera vez que se calcula, de modo que las llamadas posteriores lo recuperan en O(1) en lugar de volver a calcularlo.

Añada un diccionario memo como parámetro (o utilice una clausura). Antes de realizar el cálculo, compruebe si la respuesta ya está en memo. Si es así, devuélvala inmediatamente. Si no, calcúlela, almacénela en memo y devuélvala. Ahora cada subproblema único se calcula exactamente una vez, lo que transforma O(2^n) en un tiempo de O(n) y un espacio de O(n) para el diccionario memo, además de un espacio de pila de O(n).

Python proporciona @functools.lru_cache(maxsize=None) (también disponible como @functools.cache en Python 3.9+) para automatizar la memoización. Al añadir este decorador encima de una función, se almacenan en caché todas las llamadas según sus argumentos. maxsize=None significa que el tamaño de la caché es ilimitado: se almacena en caché cada combinación única de argumentos. Esto convierte cualquier función recursiva en una versión memoizada con una sola línea de código.

LeetCode 70 «Climbing Stairs»: puede subir 1 o 2 escalones cada vez. ¿Cuántas formas hay de llegar al escalón n? En realidad, se trata de Fibonacci: ways(n) = ways(n-1) + ways(n-2). Casos base: ways(0) = 1 (hay una forma de permanecer en el suelo) y ways(1) = 1. Con memoización, el tiempo de ejecución es O(n) y el espacio es O(n).

LeetCode 322 «Coin Change»: dadas unas denominaciones y una cantidad objetivo, encuentre el número mínimo de monedas. Recursividad memoizada de arriba abajo: dp(amount) = 1 + min(dp(amount - coin)) para cada moneda válida. El caso base es dp(0) = 0. Almacene en caché cada subcantidad. Si una subcantidad es imposible, devuelva infinito. La memoización transforma la fuerza bruta exponencial en un tiempo de O(amount × len(coins)).

LeetCode 139 «Word Break»: determine si una cadena puede segmentarse en palabras del diccionario. La recursividad de arriba abajo: can_break(s, start) prueba cada prefijo s[start:end]; si está en el diccionario y can_break(s, end) es true, devuelve true. Sin memoización, esto es O(2^n); con memoización (almacenando en caché cada índice de inicio), pasa a ser O(n² × L), donde L es la longitud máxima de palabra.

La memoización (de arriba abajo) comienza con el problema original y almacena en caché las respuestas a medida que se descubren recursivamente. Solo resuelve los subproblemas que realmente se necesitan. La tabulación (de abajo arriba) rellena previamente una tabla desde los subproblemas pequeños hasta los grandes, resolviendo todos los subproblemas. La memoización es más fácil de derivar a partir de una solución recursiva; la tabulación evita las limitaciones de profundidad de la recursividad y la sobrecarga de las llamadas a funciones.

Muchos problemas de DP que la recursividad memoizada resuelve usando un espacio O(n) pueden optimizarse aún más hasta un espacio O(1) cuando solo se necesita un número fijo de respuestas de subproblemas anteriores. En Fibonacci, solo importan los dos últimos valores. En el problema de subir escaleras ocurre lo mismo. Dos variables deslizantes sustituyen al diccionario memo o a la tabla completos.

Hay tres formas de implementar manualmente la memoización. Un diccionario global es sencillo, pero contamina el ámbito del módulo. Una clausura encapsula la caché dentro de la función, evitando fugas, pero requiere un wrapper. @lru_cache es la opción más limpia: un decorador sustituye todo el código repetitivo. En una entrevista, comience con @lru_cache, a menos que el entrevistador le pida específicamente una implementación manual.

La memoización solo acelera los problemas con subproblemas superpuestos, es decir, los casos en los que el mismo subproblema se calcula varias veces. Si cada subproblema es único (como en un recorrido simple de árbol, donde cada nodo se visita exactamente una vez), la memoización añade sobrecarga sin aportar ningún beneficio. Además, la memoización no puede resolver problemas en los que el árbol de recursión es exponencial respecto al número de subproblemas distintos en lugar de serlo debido a la reutilización; esos problemas requieren un algoritmo completamente diferente.

Aplique memoización cuando: tenga una solución recursiva correcta pero lenta debido a cálculos repetidos; la función tenga un número reducido de combinaciones distintas de argumentos; y el valor devuelto dependa únicamente de los argumentos (una función pura, sin efectos secundarios ni estado global). Compruebe el espacio de estados de los subproblemas: si hay como máximo O(n) u O(n²) estados distintos, la memoización transforma el tiempo exponencial en polinómico.

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección ha aprendido que: la memoización almacena los resultados de los subproblemas para evitar volver a calcularlos, transformando la recursividad exponencial en tiempo polinómico; @functools.lru_cache es la herramienta idiomática de Python y solo requiere una línea; y la memoización (de arriba abajo) y la tabulación (de abajo arriba) son los dos estilos de DP: la memoización es más fácil de derivar y la tabulación evita los problemas de profundidad de la pila. ¡Enhorabuena! Ha completado los módulos de recursividad y mapas hash.