DSA problem
Fibonacci Number
The Fibonacci sequence is defined by the recurrence F(n) = F(n - 1) + F(n - 2) with base cases F(0) = 0 and F(1) = 1. Given a non-negative integer n, return F(n).
A direct top-down recursive translation of the definition is correct but disastrously slow: it recomputes the same subproblems exponentially many times, giving O(2^n) calls. A classic case of "the algorithm is right, but it does the same work over and over."
Memoization caches each F(k) the first time it is computed, dropping the runtime to O(n). Even better is the bottom-up tabulation: start from the base cases and build forward, computing each F(i) exactly once in a simple loop.
The optimal approach observes that at every step the only inputs needed are the previous two values. So we keep two rolling variables a and b and update them with a, b = b, a + b for n iterations. This drops the space from O(n) to O(1) while retaining O(n) time, which is the canonical "bottom-up rolling-variable" 1-D DP pattern.
Examples
n = 21n = 32n = 43Constraints
- 0 <= n <= 30
- F(0) = 0 and F(1) = 1 by definition.
- The recurrence F(n) = F(n - 1) + F(n - 2) holds for n >= 2.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.