From the course: Fundamentals of Dynamic Programming
Join today to access over 22,600 courses taught by industry experts.
Speeding up calculations with memoization - Python Tutorial
From the course: Fundamentals of Dynamic Programming
Speeding up calculations with memoization
- The straightforward recursive implementation of the Fibonacci sequence is slow, because many of the computations are done more than once. For example, not only is the Fibonacci number with index three, that is F of three calculated twice, but each time, it takes the same number of calculations to compute. One way to get around this repeated work, is memoization. Memoization is a technique for speeding up computations by caching results of repeated calculations or sub problems. This way, when the same calculation has to be performed a second time, the result can be quickly looked up in the cache, instead of performing that calculation again. Let's see how we can apply memoization, to the Fibonacci sequence computation. We want to maintain a cache, typically represented as a dictionary or hash map. Suppose we want to calculate F of three. We start by checking, is the input three in the cache already. If yes, simply return…
Practice while you learn with exercise files
Download the files the instructor uses to teach the course. Follow along and learn by watching, listening and practicing.
Download courses and learn on the go
Watch courses on your mobile device without an internet connection. Download courses using your iOS or Android LinkedIn Learning app.