Memoización frente a tabulación
Dos formas de almacenar respuestas de subproblemas
Memoización frente a tabulación es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 1 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 Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Por qué usar caché
La recursión ingenua repite el mismo trabajo una y otra vez. La programación dinámica almacena cada respuesta una sola vez para no volver a calcularla.
fib(40) # slow: recomputes endlesslySubproblemas superpuestos
La programación dinámica se aplica cuando un problema se divide en subproblemas superpuestos. El mismo caso pequeño aparece en muchas ramas de la recursión.
fib(5) needs fib(3) twiceDe arriba abajo: memoización
La memoización es recursión normal más una caché. Calcula los resultados bajo demanda y recuerda el resultado la primera vez que encuentra cada entrada.
memo = {}Memoización sencilla en Python
El decorador lru_cache convierte la recursión lenta en programación dinámica rápida con una sola línea, almacenando automáticamente en caché cada llamada.
from functools import lru_cache
@lru_cache(None)
def f(n): ...De abajo arriba: tabulación
La tabulación rellena una tabla desde los casos más pequeños hasta la respuesta, usando un bucle en lugar de recursión.
dp = [0] * (n + 1)Un Fibonacci tabulado
Establezca los valores base y deje que cada celda lea los valores ya calculados. Sin pila de llamadas, solo un bucle claro.
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]La misma respuesta, un estilo diferente
La memoización y la tabulación resuelven la misma recurrencia. Solo difieren en la dirección: de arriba abajo bajo demanda o de abajo arriba en orden.
Cuándo preferir la memoización
Opte por la memoización cuando la recurrencia sea natural de escribir y quizá no necesite todos los estados.
Cuándo preferir la tabulación
Elija la tabulación para obtener bucles ajustados, evitar errores por el límite de recursión y cuando vaya a calcular toda la tabla de todos modos.
import sys; sys.setrecursionlimit(10**6)Preste atención al límite de recursión
Una recursión con memoización demasiado profunda puede alcanzar el límite de recursión de Python y fallar con un veredicto de error en tiempo de ejecución para entradas grandes.
Ambas comparten un costo
En ambos casos, la mejora de velocidad proviene de resolver cada estado una sola vez. El tiempo total es el número de estados multiplicado por el trabajo de cada estado.
Comprobación rápida
¿Qué enfoque rellena una tabla de abajo arriba mediante un bucle?
Repaso: dos caminos, una DP
Ahora puede almacenar subproblemas en caché de dos formas. La memoización usa recursión de arriba abajo; la tabulación usa bucles de abajo arriba. Elija la que resulte más clara. ✨
Preguntas frecuentes
¿La lección «Memoización frente a tabulación» es gratis?
Sí — el texto completo de «Memoización frente a tabulació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 Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Memoización frente a tabulación»?
Dos formas de almacenar respuestas de subproblemas Practicas Competitive Programming Academy 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 Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy 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 1 de 4.
¿Cuánto tiempo toma la lección «Memoización frente a tabulació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 Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy 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
- Memoización frente a tabulación
- Defina el estado y la transición
- Escaleras y combinaciones de monedas
- Subsecuencia creciente más larga