Programación dinámica

Programación dinámica: la programación dinámica se divide en los siguientes pasos:

Este método de almacenar los resultados de los cálculos para su reutilización se llama Memoización (no sé cómo traducir esta palabra)

Tomar la secuencia de Fibonacci como ejemplo:

1. Utilice la recursividad para implementar:

Este método es una operación recursiva clásica. Tomando fib (5) como ejemplo, todo el proceso de solución se puede dividir en:

Podemos ver que fib (2) se calcula tres veces y fib (3) y fib (1). dos veces cada uno. La complejidad del tiempo es O (2 n).

2. Mejorar la recursividad.

3. De la recursividad:

El algoritmo mejorado ya no utiliza la recursividad y la complejidad del tiempo sigue siendo O(n).

Escribe casos de prueba para las tres implementaciones anteriores:

Accidentalmente vi este video en Youtube, así que lo traduje y lo compartí con todos.