How to Solve Fibonacci Sequence Using Dynamic Programming
A brief introduction to dynamic programming by solving the Fibonacci number sequence.
Published in
7 min readFeb 21, 2021
Dynamic programming is a commonly studied concept in Computer Science. It is not an algorithm. Rather it is an algorithmic technique to solve optimization and counting problems. Dynamic programming was introduced by American mathematician Richard Bellman. The name “dynamic” has nothing to do with the actual process.
There is nothing dynamic in dynamic programming!
It is just a name Richard Bellman gave. So no need to get confused by the name.
To get started with the concept of dynamic programming an ideal example can be solving the Fibonacci number sequence. As it is very easy to understand. In this article, we will solve the Fibonacci sequence using the idea of dynamic programming.
Table of Contents:· What is Dynamic Programming
· The Fibonacci Sequence
· Solving the Problem Recursively
· The Recursion Tree
· The Dynamic Programming Approach
· The Iterative Approach
· Comparing the Complexity of Recursive Approach and Dynamic Programming Approach
· Conclusion
· Resources
