Fibonacci Number

Intuition

The plain recursive definition branches into two calls whose subtrees overlap heavily, repeating identical work. Remembering each F(k) after computing it once removes the duplication and turns what would be exponential work into a single linear pass over the indices.

Algorithm walkthrough

1. 1For any index below 2, return the index itself (F(0) = 0, F(1) = 1).
2. 2Keep a cache initialized to a sentinel value meaning 'unknown'.
3. 3When F(k) is requested and already cached, return the cached value.
4. 4Otherwise compute F(k-1) + F(k-2), store the result, and return it.

Implementation

class Solution:
    def fib(self, n: int) -> int:
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def f(k: int) -> int:
            if k < 2:
                return k
            return f(k - 1) + f(k - 2)

        return f(n)

Intuition

Each Fibonacci number is fully determined by the two before it, so keeping just those two around is enough. A single loop advances the pair from the base cases up to the target index without any extra storage.

Algorithm walkthrough

1. 1If n is below 2, return n directly.
2. 2Start a = F(0) = 0 and b = F(1) = 1.
3. 3For each index from 2 to n, set next = a + b.
4. 4Move the window forward: a becomes b and b becomes next.
5. 5Return b, which now holds F(n).

Implementation

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 b