Memoizing Fibonacci Numbers

In this lesson, we are going to reduce the time complexity of the Fibonacci code we wrote using a dynamic programming technique called memoization.

We'll cover the following

Memoized code
Improvement in time complexity

In the last lesson, we introduced the basic concept of dynamic programming and its two patterns: memoization and tabulation.

In the first lesson of this chapter, we established that the recursive implementation of the Fibonacci sequence causes calculations, which result in exponential time complexity.

Let’s memoize the code now and see where that leads us. The basic idea is to check if an array already contains the result of the Fibonacci number that we are trying to find before calculating it.

Memoized code

Have a look at the complete code in Java:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.

Introduction

Algorithmic Paradigms

Asymptotic Analysis

Sorting and Searching

Dynamic Programming

Greedy Algorithms

Divide and Conquer

Graph Algorithms

Appendix: Auxiliary Source Code

Conclusion

Memoizing Fibonacci Numbers

Memoized code