Así es como se utiliza:
1. Identificación de subproblemas superpuestos: La programación dinámica resuelve problemas al descomponerlos en subproblemas más pequeños y superpuestos. Si se encuentra el mismo subproblema varias veces, la memorización puede evitar la recalculación.
2. Resultados de almacenamiento: Se utiliza una estructura de datos, generalmente una tabla hash (diccionario en Python) o una matriz, para almacenar los resultados de subproblemas. La entrada al subproblema (por ejemplo, los parámetros de una función recursiva) sirve como clave, y el resultado calculado es el valor.
3. Comprobación de resultados en caché: Antes de calcular la solución a un subproblema, el algoritmo verifica el almacenamiento para ver si el resultado ya está disponible. Si es así, el resultado almacenado en caché se devuelve de inmediato.
4. Resultados de almacenamiento y devolución: Si el resultado no se almacena en caché, el algoritmo lo calcula, lo almacena en la estructura de datos y luego lo devuelve.
Ejemplo (secuencia Fibonacci):
Una solución ingenua recursiva para la secuencia Fibonacci es altamente ineficiente debido a los cálculos repetidos. La memoización mejora drásticamente esto:
Solución recursiva ingenua (ineficiente):
`` `Python
Def fibonacci_naive (n):
Si n <=1:
regresar n
return fibonacci_naive (N-1) + fibonacci_naive (N-2)
`` `` ``
Solución recursiva memoizada:
`` `Python
Memo ={} # diccionario para la memoización
Def fibonacci_memo (n):
Si n en memo:
Return Memo [N]
Si n <=1:
resultado =n
demás:
resultado =Fibonacci_Memo (N-1) + Fibonacci_Memo (N-2)
Memo [n] =resultado
Resultado de retorno
`` `` ``
En la versión memoizada:
* `Memo` almacena números de fibonacci previamente calculados.
* Antes de hacer una llamada recursiva, las verificaciones `fibonacci_memo` si el resultado para` n` ya está en `memo`.
* Si es así, el valor almacenado se devuelve directamente. De lo contrario, el resultado se calcula, se almacena en `Memo` y luego se devuelve.
Este cambio transforma un algoritmo de tiempo exponencial en un algoritmo de tiempo lineal. La clave es evitar los cálculos redundantes de los mismos números de Fibonacci varias veces.
en esencia: La memoización transforma un enfoque de programación dinámica de arriba hacia abajo (recursivo) en uno más eficiente al almacenar en caché los resultados intermedios. Complementa enfoques de tabulación (de abajo hacia arriba), que también evitan los cálculos redundantes pero usan métodos iterativos en lugar de recursión. La elección entre memoización y tabulación a menudo depende del problema específico y la preferencia del programador; Ambos logran el mismo objetivo de evitar cálculos redundantes.