Learn Fibonacci Series using Dynamic Programming with top-down (memoization) and bottom-up (tabulation) approaches, algorithms, complexity analysis, and examples.
Fibonacci Series Using Dynamic Programming:
Introduction to Fibonacci Series
The Fibonacci Series is a sequence of numbers in which:
- The first two numbers are 0 and 1
- Each subsequent number is the sum of the previous two numbers
Mathematical Formula:
F(n)=F(n−1)+F(n−2)F(n) = F(n – 1) + F(n – 2)F(n)=F(n−1)+F(n−2)
Where:
- F(0)=0F(0) = 0F(0)=0
- F(1)=1F(1) = 1F(1)=1
Problems in Recursive Method
In the recursive approach, the same Fibonacci values are computed repeatedly.
This results in:
- Creation of overlapping subproblems
- Very high time complexity
- Excessive recursive function calls
Time Complexity of Recursive Method:
O(2n)O(2^n)O(2n)
Hence, the recursive method is inefficient for large values of n.
Why Use Dynamic Programming for Fibonacci Series?
The Fibonacci problem satisfies both properties required for Dynamic Programming:
- Overlapping Subproblems
Same Fibonacci values are computed multiple times. - Optimal Substructure
The solution of F(n)F(n)F(n) depends on optimal solutions of F(n−1)F(n-1)F(n−1) and F(n−2)F(n-2)F(n−2).
Therefore, Fibonacci Series is an ideal example of Dynamic Programming.
Fibonacci Series – Two Approaches of Dynamic Programming
(A) Top-Down Approach (Memoization)
In this approach:
- A recursive function is used
- After computing a Fibonacci value, it is stored in an array
- If the same value is required again, it is returned directly from memory
Algorithm (Top-Down Approach):
Fibonacci(n)
if n ≤ 1
return n
if fib[n] is already computed
return fib[n]
fib[n] = Fibonacci(n−1) + Fibonacci(n−2)
return fib[n]
Time Complexity: O(n)
Space Complexity: O(n)
(B) Bottom-Up Approach (Tabulation)
In this approach:
- Smallest subproblems are solved first
- Results are stored in a table
- No recursion is used
Algorithm (Bottom-Up Approach):
Fibonacci(n)
fib[0] = 0
fib[1] = 1
for i = 2 to n
fib[i] = fib[i−1] + fib[i−2]
return fib[n]
Time Complexity: O(n)
Space Complexity: O(n)
Generally, the Bottom-Up approach is more efficient because it avoids recursion overhead.
Example
If n = 6, then Fibonacci Series is:
0,1,1,2,3,5,80, 1, 1, 2, 3, 5, 80,1,1,2,3,5,8
Advantages of Using Dynamic Programming
- Redundant calculations are avoided
- Time complexity is reduced from O(2ⁿ) to O(n)
- Efficient memory usage
- Faster and more scalable solution
Conclusion
The Fibonacci Series is a classic example used to explain Dynamic Programming concepts.
Because it exhibits both overlapping subproblems and optimal substructure, Dynamic Programming provides an efficient and optimal solution.
Understanding Fibonacci using DP helps in learning more complex Dynamic Programming problems.
Some More:
- POP- Introduction to Programming Using ‘C’
- DS – Data structure Using C
- OOP – Object Oriented Programming
- Java Programming
- DBMS – Database Management System
- RDBMS – Relational Database Management System
- https://defineinfoloop.blogspot.com/?m=1