1D Dynamic Programming - Fibonacci
Dynamic Programming (DP) is a powerful technique for solving complex problems by breaking them down into simpler, overlapping subproblems. The Fibonacci sequence is a classic example used to introduce DP concepts.
The Fibonacci Sequence
The Fibonacci sequence is defined as follows:
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) for n > 1
A naive recursive solution would have an exponential time complexity of O(2^n) due to repeated calculations.
Bottom-Up DP Approach
A more efficient approach is to use bottom-up dynamic programming, which involves:
- Initialization: Create a table (or array) to store the results of subproblems.
- Base Cases: Fill in the initial values, F(0) and F(1).
- Iteration: Iterate from 2 to n, calculating each Fibonacci number using the previously stored values.
This approach has a linear time complexity of O(n) and a space complexity of O(n).
Interactive Fibonacci DP Visualization
The visualization below demonstrates the bottom-up dynamic programming approach to calculating the Fibonacci sequence.
Fibonacci Dynamic Programming
N =
Current Step
1 of 0
Computing
F(5)
DP Operations
0
Result
?
Current Operation
Dynamic Programming Table
F(0)
?
Not computed
F(1)
?
Not computed
F(2)
?
Not computed
F(3)
?
Not computed
F(4)
?
Not computed
F(5)
?
Not computed
Each cell stores the result to avoid recomputation
Fibonacci Sequence
[?,?,?,?,?,?]
Dynamic Programming
Time Complexity:O(n)
Space Complexity:O(n)
Operations for F(5):6
✅ Each subproblem solved exactly once
Naive Recursion
Time Complexity:O(2^n)
Space Complexity:O(n)
Operations for F(5):15
❌ Many subproblems solved repeatedly
Optimal Substructure
F(n) = F(n-1) + F(n-2)
Solution depends on optimal solutions to subproblems
Solution depends on optimal solutions to subproblems
Overlapping Subproblems
F(n-1) and F(n-2) share many subproblems
Store results to avoid recomputation
Store results to avoid recomputation
Dynamic Programming: Breaks complex problems into simpler subproblems and stores their solutions. For Fibonacci: instead of recalculating F(n-1) and F(n-2) repeatedly, we build up from F(0) and F(1), storing each result. This reduces exponential time to linear time!