← Back to DSA Animator
Fibonacci Number LC #509 Easy DP · Iterative
Problem

The Fibonacci numbers: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Given n, return F(n).

Example
n=5 → F(5)=5 (0,1,1,2,3,5)
Constraints: 0 ≤ n ≤ 30
Try Examples
Custom n:
Approach
Iterative DP — Two Rolling Variables
Build fib(n) bottom-up: c = a + b, then a=b, b=c. No array needed since we only look back 2 steps.
Fibonacci Sequence
Load an example.
Variables
i
—
a (fib i-2)
—
b (fib i-1)
—
fib(n)
—
Step Logic
Press ▶ Play or Next Step to begin.
🔢
Ready
0 / 0
Select an example and press Play.
Algorithm
1
fib(0)=0, fib(1)=1 (base)
2
For i=2..n: c=a+b, a=b, b=c
3
Return b (fib(n))
Time
O(n)
Space
O(1)
Why This Works

Instead of recursive calls, we build the sequence iteratively. We only need the last two values (a, b) to compute the next, so no memoization array is needed — O(1) space.