Posterior a de una extensa selección de datos pudimos resolver este dilema que presentan muchos usuarios. Te brindamos la respuesta y nuestro deseo es resultarte de mucha apoyo.
Solución:
Artículo relevante sobre Programación. Guía: Programación dinámica vs memorización vs tabulación
¿Cuál es la diferencia entre memorización y programación dinámica?
Memoización es un término que describe una técnica de optimización en la que almacena en caché los resultados calculados previamente y devuelve el resultado almacenado en caché cuando se necesita el mismo cálculo nuevamente.
Programación dinámica es una técnica para resolver problemas de naturaleza recursiva, iterativamente y es aplicable cuando los cálculos de los subproblemas se superponen.
La programación dinámica es típicamente implementado usando tabulación, pero también puede implementarse usando memorización. Entonces, como puede ver, ninguno es un “subconjunto” del otro.
Una pregunta de seguimiento razonable es: ¿Cuál es la diferencia entre tabulación (la típica técnica de programación dinámica) y memorización?
Cuando resuelves un problema de programación dinámica usando tabulación, resuelves el problema “de abajo hacia arriba“, es decir, resolviendo primero todos los subproblemas relacionados, típicamente llenando un norte-tabla dimensional. Con base en los resultados de la tabla, se calcula la solución al problema “superior”/original.
Si usa la memorización para resolver el problema, lo hace manteniendo un mapa de subproblemas ya resueltos. Hazlo tu “De arriba hacia abajo” en el sentido de que primero resuelve el problema “superior” (que generalmente se repite hacia abajo para resolver los subproblemas).
Una buena diapositiva de aquí (el enlace ahora está muerto, aunque la diapositiva sigue siendo buena):
- Si todos los subproblemas deben resolverse al menos una vez, un algoritmo de programación dinámica de abajo hacia arriba generalmente supera a un algoritmo memorizado de arriba hacia abajo por un factor constante
- Sin gastos generales para la recursividad y menos gastos generales para mantener la tabla
- Hay algunos problemas para los cuales el patrón regular de accesos a tablas en el algoritmo de programación dinámica puede explotarse para reducir aún más los requisitos de tiempo o espacio.
- Si no es necesario resolver algunos subproblemas en el espacio de subproblemas, la solución memorizada tiene la ventaja de resolver solo aquellos subproblemas que definitivamente se requieren.
Recursos adicionales:
- Wikipedia: memorización, programación dinámica
- Preguntas y respuestas relacionadas con SO: enfoque de memorización o tabulación para la programación dinámica
La programación dinámica es un paradigma algorítmico que resuelve un problema complejo determinado dividiéndolo en subproblemas y almacena los resultados de los subproblemas para evitar calcular los mismos resultados nuevamente.
http://www.geeksforgeeks.org/dynamic-programming-set-1/
La memorización es un método fácil para rastrear soluciones previamente resueltas (a menudo implementadas como un hash key par de valores, a diferencia de la tabulación, que a menudo se basa en matrices) para que no se vuelvan a calcular cuando se vuelvan a encontrar. Se puede utilizar tanto en métodos de abajo hacia arriba como de arriba hacia abajo.
Vea esta discusión sobre memorización versus tabulación.
Entonces, la programación dinámica es un método para resolver ciertas clases de problemas resolviendo relaciones de recurrencia/recursión y almacenando soluciones encontradas previamente mediante tabulación o memorización. La memorización es un método para realizar un seguimiento de las soluciones a problemas resueltos previamente y se puede utilizar con cualquier función que tenga soluciones deterministas únicas para un conjunto dado de entradas.
¡La programación dinámica a menudo se llama memorización!
-
La memorización es la técnica de arriba hacia abajo (comienza a resolver el problema dado dividiéndolo) y la programación dinámica es una técnica de abajo hacia arriba (comienza a resolver desde el subproblema trivial hacia el problema dado)
-
DP encuentra la solución a partir de los casos base y avanza hacia arriba. DP resuelve todos los subproblemas, porque lo hace de abajo hacia arriba
A diferencia de Memoization, que resuelve solo los subproblemas necesarios
-
DP tiene el potencial de transformar soluciones de fuerza bruta de tiempo exponencial en algoritmos de tiempo polinomial.
-
DP puede ser mucho más eficiente porque es iterativo
Por el contrario, Memoization debe pagar los gastos generales (a menudo significativos) debido a la recursividad.
Para ser más simple, Memoization utiliza el enfoque de arriba hacia abajo para resolver el problema, es decir, comienza con el problema central (principal) y luego lo divide en subproblemas y resuelve estos subproblemas de manera similar. En este enfoque, el mismo subproblema puede ocurrir varias veces y consumir más ciclos de CPU, por lo tanto, aumenta la complejidad del tiempo. Mientras que en la programación dinámica, el mismo subproblema no se resolverá varias veces, pero el resultado anterior se utilizará para optimizar la solución.