DSA AnimatorDSA animations
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.

How to solve Fibonacci Number

LeetCode 509 · Easy · Dynamic Programming · Pattern: 1D DP

Why the obvious approach is slow

The direct recursion calls F of n −1 and F of n minus 2, and each of those calls two more. The same values are computed again and again, so the time grows like 2 to the power n. For example, F of 3 alone is computed three times while finding F of 6.

The key idea

This is the core idea of dynamic programming: solve each small problem once and store the answer. Build the values from the bottom up, starting with F of 0 and F of 1. Each new value only needs the previous two. So instead of a whole array, two variables are enough.

Remember

Overlapping subproblems are the signal for dynamic programming. Keep only the states the next step needs.

Run the animation above on your own input, or watch the 1:47 video explanation of Fibonacci Number with a dry run and Java code.

More Dynamic Programming problems