Fibonacci

1 problem using this pattern

About this pattern:

A useful algorithmic pattern for solving coding problems efficiently.

Often used with: Dynamic Programming

Complexity Range

Time Complexity

O(n) (1 problem)

Space Complexity

O(1) (1 problem)

Problems Using Fibonacci

Climbing Stairs

Count distinct ways to climb n stairs (1 or 2 steps at a time).

Easy LeetCode
Time:
O(n)?
Why O(n)?
We calculate each step once from 2 to n
Instead of naive recursion (exponential), we use bottom-up DP to compute each step exactly once.
Example: For n=50, we do 48 iterations instead of 2^50 recursive calls
Space:
O(1)?
Why O(1)?
Only storing the last two values
We optimize space by only keeping prev2 and prev1 instead of an entire DP array.
Example: Uses same memory for n=10 or n=10,000
Example: n = 3 → 3 (1+1+1, 1+2, 2+1)
Dynamic Programming Fibonacci
View Solution →
← Back to All Patterns
View All Categories