Fibonacci Number
Iterative two-variable rolling — O(1) space.
2 min read
dp math recursion
Problem#
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n >= 2. Return F(n).
Examples#
n=2→1;n=3→2;n=4→3.
Constraints#
0 <= n <= 30.
Approach#
Iterative two-variable rolling.
Solution#
class Solution {public: int fib(int n) { if (n < 2) return n; int a = 0, b = 1; for (int i = 2; i <= n; ++i) { int c = a + b; a = b; b = c; } return b; }};func fib(n int) int { if n < 2 { return n } a, b := 0, 1 for i := 2; i <= n; i++ { a, b = b, a+b } return b}class Solution: def fib(self, n: int) -> int: if n < 2: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return bfunction fib(n) { if (n < 2) return n; let a = 0, b = 1; for (let i = 2; i <= n; i++) { [a, b] = [b, a + b]; } return b;}class Solution { public int fib(int n) { if (n < 2) return n; int a = 0, b = 1; for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; } return b; }}function fib(n: number): number { if (n < 2) return n; let a = 0, b = 1; for (let i = 2; i <= n; i++) { [a, b] = [b, a + b]; } return b;}Editorial#
The naive recursive O(2^n) is the textbook example of overlapping subproblems. Iterating bottom-up with two rolling values is the canonical O(n) time, O(1) space form. Closed-form via matrix exponentiation gets O(log n) if needed.
Complexity#
- Time:
O(n). - Space:
O(1).
Concept revision#
Related#