¿Cuál es la diferencia entre programación dinámica y recursión + memorización? ¿Cuál es más rápido? (Asumiendo que el problema puede ser resuelto por ambos).


Respuesta 1:

Tu comprensión de la programación dinámica es incorrecta. La memorización y la tabulación son técnicas de almacenamiento. La programación dinámica es la resolución de la relación de recurrencia / recursiones mediante el almacenamiento de soluciones previamente resueltas.

La memorización se puede utilizar para enfoques de arriba hacia abajo y de abajo hacia arriba.

Entonces, su pregunta real es: cuando el uso de la programación dinámica es un enfoque ascendente o un enfoque descendente más rápido.

La respuesta es, depende.

Cuando se utilizan enfoques ascendentes, el riesgo es que puede resolver soluciones que nunca son necesarias.

Al usar enfoques de arriba hacia abajo, debe colocar cada llamada de función en la pila, con el enfoque típico (existen soluciones alternativas que complican las cosas significativamente), la profundidad de recursión puede exceder sus recursos y, por lo tanto, fallar.

En general, esperaría que la memorización de arriba hacia abajo sea más rápida que la tabulación o memorización de abajo hacia arriba.