Nth Fibonacci
Medium · rating 1200 · dp, math
Read an integer n (0 ≤ n ≤ 90). Print the n-th Fibonacci number, where F(0) = 0, F(1) = 1.
Editorial
Nth Fibonacci Number is a classic introduction to dynamic programming: each number is the sum of the previous two, with F(0) = 0 and F(1) = 1.
Approach
Naïve recursion is O(2ⁿ) because it recomputes the same subproblems. Iterate bottom-up instead, carrying just the last two values — no array required.
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return aGoing further
Fibonacci can be computed in O(log n) with matrix exponentiation or fast doubling — a nice interview follow-up.
Complexity
Time: O(n). Space: O(1).