EasyDynamic ProgrammingRecursionMemoizationMath

Fibonacci Number

2 approaches, code in every language

The Fibonacci numbers start with F(0) = 0 and F(1) = 1, and after that every number is the sum of the two immediately before it: F(n) = F(n - 1) + F(n - 2) for n greater than 1.

Given an index n, return the value F(n).

Example 1

Input: n = 2

Output: 1

F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2

Input: n = 5

Output: 5

The sequence up to index 5 is 0, 1, 1, 2, 3, 5, so F(5) = 5.

Constraints

0 ≤ n ≤ 30
The result fits inside a signed 32-bit integer.

Top-down recursion with memoization

Recurse on the definition but cache each F(k) so the overlapping subproblems are computed only once.

Loading animation…

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

1For any index below 2, return the index itself (F(0) = 0, F(1) = 1).
2Keep a cache initialized to a sentinel value meaning 'unknown'.
3When F(k) is requested and already cached, return the cached value.
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)

Time

O(n)

Space

O(n)

Bottom-up with two rolling variables

Carry only the previous two Fibonacci values forward in a single loop.

Loading animation…

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

1If n is below 2, return n directly.
2Start a = F(0) = 0 and b = F(1) = 1.
3For each index from 2 to n, set next = a + b.
4Move the window forward: a becomes b and b becomes next.
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

Time

O(n)

Space

O(1)

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Cascade Register Reading is our own problem on the technique behind Fibonacci Number: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free

Fibonacci Number

Problem description

Example 1

Example 2

Constraints

Create a free account to see the solution

Now solve one you haven't seen.