0Pricing
Coding Interview Prep · Lección

DP top-down con memoización

Añada un diccionario memo a una solución recursiva para podar llamadas duplicadas y use @lru_cache para memoizar con un mínimo de código.

DP top-down con memoización es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.

DP de arriba abajo: la idea de la memoización

La DP de arriba abajo parte de la solución recursiva original y añade memoización: una caché que almacena el resultado de cada subproblema la primera vez que se calcula. En llamadas posteriores con los mismos argumentos, el resultado almacenado se devuelve inmediatamente, sin recursión. Esto transforma una recursión ingenua de O(2^n) en O(n) con cambios mínimos en el código: a menudo basta con añadir 2 o 3 líneas a una solución recursiva existente.

# Top-down approach:
# 1. Write the recursive solution (natural but slow)
# 2. Add a memo dict to cache results
# 3. Before recursing, check if the result is cached
# 4. Before returning, store the result in the cache

# This is also called 'memoization' (US spelling)
# 'memoize' means 'to remember', not 'memorize'

# The cache key is the function arguments
# For fib: key is n
# For 2D DP: key is (i, j)
# For 3D DP: key is (i, j, k)
print('Top-down = recursion + memo cache')

Fibonacci con memoización

Añadir un diccionario de memoización a la recursión ingenua de Fibonacci reduce el tiempo de O(2^n) a O(n). La primera llamada a fib(k) calcula y almacena el resultado. Todas las llamadas posteriores para el mismo k devuelven inmediatamente el valor almacenado en caché. La complejidad espacial es O(n) para el diccionario de memoización, además de O(n) para la pila de llamadas. Compare el número de llamadas: sin memoización, fib(30) realiza aproximadamente 2 millones de llamadas; con memoización, exactamente 30 llamadas.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]  # return cached result
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# Verify speed improvement:
print(fib_memo(30))   # fast!
print(fib_memo(50))   # still fast
print(fib_memo(100))  # no problem

# Without memo, fib_naive(50) would take minutes
# With memo: each of the 50 sub-problems computed once

Uso de @functools.lru_cache

El decorador de Python @functools.lru_cache(maxsize=None) (o el alias @cache en Python 3.9 y versiones posteriores) aplica memoización automáticamente a una función en función de sus argumentos. Esta es la forma más limpia de añadir DP de arriba abajo en una entrevista: escriba la solución recursiva, añada el decorador y listo. El decorador almacena todos los resultados en un diccionario cuyas claves son los argumentos de la función, que deben ser hashable (no listas; use tuplas).

import functools

@functools.lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

print(fib(50))   # 12586269025
print(fib(100))  # works instantly

# Clear cache between tests if needed:
fib.cache_clear()

# Python 3.9+ shorthand:
# from functools import cache
# @cache
# def fib(n): ...

print(fib.cache_info())  # shows hits, misses, maxsize, currsize

Cambio de monedas de arriba abajo

Cambio de monedas (LeetCode #322): dadas unas denominaciones de monedas y una cantidad objetivo, encuentre el número mínimo de monedas necesario. La formulación recursiva consiste en tomar cada moneda y resolver el problema para la cantidad restante; después, se toma el mínimo. Aplique memoización sobre la cantidad para evitar recalcular resultados. Caso base: amount=0 necesita 0 monedas; una cantidad imposible devuelve infinito (o -1 después de la recursión).

import functools

def coin_change_top_down(coins, amount):
    @functools.lru_cache(maxsize=None)
    def dp(remaining):
        if remaining == 0:
            return 0  # no coins needed
        if remaining < 0:
            return float('inf')  # impossible
        # Try each coin and take the minimum
        return 1 + min(dp(remaining - c) for c in coins)

    result = dp(amount)
    return result if result != float('inf') else -1

print(coin_change_top_down([1, 5, 6, 9], 11))  # 2: (5+6) or (2*5+1?no: 9+2?no) 5+6=11 YES
print(coin_change_top_down([2], 3))             # -1: impossible
print(coin_change_top_down([1, 2, 5], 11))      # 3: 5+5+1

Subir escaleras de arriba abajo con k pasos

Generalice el problema de subir escaleras para permitir de 1 a k pasos. El estado es el escalón actual y, desde el escalón i, puede llegar a los escalones i+1, i+2, ..., i+k. La recurrencia es: dp(i) = sum of dp(i-j) for j in 1..k if i-j >= 0. La memoización hace que la complejidad sea O(n*k) en lugar de O(k^n). Esta generalización aparece en problemas como «coste mínimo para llegar al último escalón» y «contar las formas de rellenar una cuadrícula».

import functools

def climb_k_steps(n, k):
    @functools.lru_cache(maxsize=None)
    def dp(i):
        if i == 0:
            return 1  # base: one way to stay at ground
        if i < 0:
            return 0  # impossible
        # From stair i, you could have come from i-1, i-2, ..., i-k
        return sum(dp(i - j) for j in range(1, k+1) if i - j >= 0)

    return dp(n)

# k=2 (original): should match fib-like sequence
print([climb_k_steps(n, 2) for n in range(7)])  # [1,1,2,3,5,8,13]
# k=3: more options
print([climb_k_steps(n, 3) for n in range(7)])  # [1,1,2,4,7,13,24]

LCS de arriba abajo: memoización 2D

La subsecuencia común más larga (LCS) requiere un estado 2D: dp(i, j) = longitud de la LCS de s1[:i] y s2[:j]. Si s1[i-1] == s2[j-1], los caracteres coinciden: dp(i,j) = 1 + dp(i-1, j-1). En caso contrario: dp(i,j) = max(dp(i-1,j), dp(i,j-1)) — omita un carácter de cualquiera de las dos cadenas. Aplicar memoización sobre (i, j) da O(mn) en lugar de O(2^(m+n)).

import functools

def lcs_top_down(s1, s2):
    m, n = len(s1), len(s2)

    @functools.lru_cache(maxsize=None)
    def dp(i, j):
        if i == 0 or j == 0:
            return 0  # empty prefix has LCS of 0
        if s1[i-1] == s2[j-1]:
            return 1 + dp(i-1, j-1)  # characters match
        return max(dp(i-1, j), dp(i, j-1))  # skip one

    return dp(m, n)

print(lcs_top_down('abcde', 'ace'))   # 3: 'ace'
print(lcs_top_down('abc', 'abc'))     # 3: 'abc'
print(lcs_top_down('abc', 'def'))     # 0: no common chars

Diccionario de memoización frente a lru_cache: cuándo elegir cada uno

Use @lru_cache cuando los argumentos de su función sean tipos primitivos hashables (int, str, tuple). Use un diccionario de memoización manual cuando necesite pasar estados mutables (listas, diccionarios) convirtiéndolos en tuplas, cuando necesite controlar qué claves ya se han calculado o cuando trabaje en un método de clase donde no deba almacenarse self en caché. El diccionario de memoización manual es más explícito y evita problemas sutiles con cierres en funciones auxiliares recursivas.

# @lru_cache: clean, automatic, O(1) overhead
# Use when: arguments are simple (int, str, tuple)
import functools
@functools.lru_cache(maxsize=None)
def simple_dp(n):
    if n <= 1: return n
    return simple_dp(n-1) + simple_dp(n-2)

# Manual memo dict: explicit, flexible
# Use when: complex state, need to inspect memo, class methods
def manual_memo_dp(s1, s2):
    memo = {}
    def dp(i, j):
        if (i,j) in memo: return memo[(i,j)]
        if i == 0 or j == 0:
            return 0
        if s1[i-1] == s2[j-1]:
            memo[(i,j)] = 1 + dp(i-1, j-1)
        else:
            memo[(i,j)] = max(dp(i-1,j), dp(i,j-1))
        return memo[(i,j)]
    return dp(len(s1), len(s2))

print(manual_memo_dp('abcde', 'ace'))  # 3

Suma objetivo de arriba abajo

Suma objetivo (LeetCode #494): asigne + o - a cada número y cuente las asignaciones que producen una suma objetivo. Estado: dp(index, current_sum). En cada índice, pruebe a sumar (+) y restar (-) el número actual. Aplicar memoización sobre (index, current_sum) transforma la fuerza bruta de O(2^n) en O(n * sum_range). El intervalo de sumas está limitado por la suma total de todos los números, lo que da O(n * S) estados en total.

import functools

def find_target_sum_ways(nums, target):
    @functools.lru_cache(maxsize=None)
    def dp(index, current_sum):
        if index == len(nums):
            return 1 if current_sum == target else 0
        # Try adding the number
        add = dp(index + 1, current_sum + nums[index])
        # Try subtracting the number
        subtract = dp(index + 1, current_sum - nums[index])
        return add + subtract

    return dp(0, 0)

print(find_target_sum_ways([1,1,1,1,1], 3))  # 5
print(find_target_sum_ways([1], 1))            # 1
print(find_target_sum_ways([1], -1))           # 1

DP de arriba abajo frente a DP de abajo arriba: ventajas y desventajas

De arriba abajo (memoización): ventajas: es natural de escribir (parte de la solución recursiva), solo calcula los subproblemas que realmente se necesitan (de forma diferida) y permite añadir la caché gradualmente. De abajo arriba (tabulación): ventajas: no tiene la sobrecarga de la pila de llamadas (ni el límite de recursión de Python), ofrece un acceso a memoria más favorable para la caché y facilita la optimización del espacio. Ambas tienen la misma complejidad asintótica. En las entrevistas, empiece por arriba abajo para verificar la corrección y, después, conviértala a una solución de abajo arriba si le piden un mejor uso del espacio.

# Top-down advantages:
# + Natural: write recursive, add @cache
# + Lazy: only computes needed sub-problems
# + Easy to reason about correctness
# - Uses call stack (recursion limit in Python)
# - Higher constant factor (function call overhead)

# Bottom-up advantages:
# + No recursion limit
# + Better cache performance (sequential memory)
# + Easier to space-optimise (rolling array)
# - Must compute all sub-problems in order
# - Less intuitive for complex 2D/3D problems

# Interview strategy:
# Start with top-down to verify recurrence,
# convert to bottom-up only if asked.
print('Top-down: easy to write | Bottom-up: efficient for large n')

Segmentación de palabras con DP de arriba abajo

Segmentación de palabras (LeetCode #139) pregunta si una cadena s puede dividirse en palabras de un diccionario. Estado: dp(i) = indica si s[i:] puede segmentarse. Desde el índice i, pruebe todas las palabras: si s[i:i+len(w)] == w, haga la recursión sobre el sufijo restante. La memoización sobre el índice inicial transforma la fuerza bruta de O(2^n) en O(n^2) (o O(n * max_word_len)) junto con la comprobación de pertenencia al conjunto.

import functools

def word_break(s, word_dict):
    word_set = set(word_dict)

    @functools.lru_cache(maxsize=None)
    def dp(start):
        if start == len(s):
            return True  # successfully segmented entire string
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and dp(end):
                return True
        return False

    return dp(0)

print(word_break('leetcode', ['leet', 'code']))       # True
print(word_break('applepenapple', ['apple', 'pen'])) # True
print(word_break('catsandog', ['cats', 'dog', 'and', 'cat', 'san', 'andog'])) # False

Límite de recursión e Itertools

El límite de recursión predeterminado de Python es 1000 (establecido por sys.getrecursionlimit()). En problemas de DP con entradas grandes (n = 10,000+), la memoización de arriba abajo alcanzará este límite. Opciones: aumente el límite con sys.setrecursionlimit(100000) o convierta la solución a DP de abajo arriba. En programación competitiva, es habitual aumentar el límite; en código de producción, prefiera siempre soluciones de abajo arriba o iterativas por motivos de fiabilidad.

import sys

print('Default recursion limit:', sys.getrecursionlimit())  # 1000

# For large DP problems, increase if needed:
# sys.setrecursionlimit(100000)

# Better: convert to bottom-up DP for large n
def fib_bottom_up(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

# No recursion limit issue:
print(fib_bottom_up(10000))  # works fine, no recursion

Comprobación rápida

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

Resumen de la lección

En esta lección aprendió: DP de arriba abajo con un diccionario de memoización y el decorador @lru_cache, soluciones con memoización para Fibonacci, cambio de monedas, LCS, suma objetivo y segmentación de palabras, y cuándo elegir una solución de arriba abajo frente a una de abajo arriba. A continuación, implementará DP de abajo arriba con tabulación y optimización del espacio.

Preguntas frecuentes

¿La lección «DP top-down con memoización» es gratis?

Sí — el texto completo de «DP top-down con memoización» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.

¿Qué aprenderé en «DP top-down con memoización»?

Añada un diccionario memo a una solución recursiva para podar llamadas duplicadas y use @lru_cache para memoizar con un mínimo de código. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Coding Interview Prep?

No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.

¿Cuánto tiempo toma la lección «DP top-down con memoización»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?

Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

  1. Reconocimiento de DP: subproblemas superpuestos
  2. DP top-down con memoización
  3. DP bottom-up con tabulación
  4. Cambio de monedas y escalera de coste mínimo
← Volver a Coding Interview Prep