Dynamic Programming · 032Easy
Fibonacci Number
The Fibonacci sequence is F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. Given n, return F(n).
Constraints
- 0 <= n <= 90 (beyond 78 the result exceeds Number.MAX_SAFE_INTEGER)
Examples
fib(2) -> 1 fib(10) -> 55 fib(0) -> 0 fib(1) -> 1 fib(3) -> 2 fib(50) -> 12586269025 // still exact in a double
Edge cases
- n = 0 and n = 1 are the base cases.
- Large n loses precision in 64-bit floats.
Show the target complexity (spoiler)
- Naive
- O(2^n) time — plain recursion, recomputing the same subproblems exponentially. Try
- Target
- O(n) time, O(1) space — iterate keeping only the last two values. (O(log n) is possible via matrix exponentiation.)
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/09-dynamic-programming/032-fibonacci.js ./practice c 032