391. Fibonacci Number
The Fibonacci sequence starts F(0) = 0, F(1) = 1, and from there every term is the sum of the two before it: F(n) = F(n − 1) + F(n − 2).
Given a non-negative integer n, return F(n).
The definition is literally a recursion — but translating it directly into code does an astonishing amount of repeated work. This problem is the classic doorway into dynamic programming: same math, none of the waste.
Example 1:
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:
Input: n = 4
Output: 3
Explanation: The sequence runs 0, 1, 1, 2, 3 — so F(4) = F(3) + F(2) = 2 + 1 = 3.
Constraints:
- 0 ≤ n ≤ 30
Hints:
The two base cases are F(0) = 0 and F(1) = 1 — everything else is the sum of the previous two. A direct recursive translation works, but count how many times it ends up computing F(2).
Each F(k) only ever has one value, so compute it once: either cache recursive results (memoization) or build up from 0 and 1 iteratively. For the iterative version you never need more than the last two values — two variables, O(1) space.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 2
Expected output: 1