From the course: Advanced Algorithmic Thinking with Python

Unlock this course with a free trial

Join today to access over 25,500 courses taught by industry experts.

Top-down dynamic programming example

Top-down dynamic programming example - Python Tutorial

From the course: Advanced Algorithmic Thinking with Python

Start my 1-month free trial Buy for my team

Top-down dynamic programming example

“

- [Instructor] The top down approach to dynamic programming generally uses memorization, which is a technique for avoiding repeat calculations. For example, if you look at the Fibonacci function, or a function for calculating Fibonacci numbers, you can see that calculating the sixth Fibonacci number requires calculating the fifth and the fourth, and the fifth involves calculating the fourth and the third, and the fourth involves calculating the third and the second. And you can see there's a large amount of repetition here. On the next slide, you can see just how much. So what we're going to do with memorization is once we've calculated a value once, we're going to store it, and then we're not going to repeat all that work of calculating again, based on all of its sub-problems. Now, if you check out branch 04_02, you'll find a file called memorization.py, and it contains three different versions of the Fibonacci…

Contents