Easy

Fibonacci Number

010

Return the nth Fibonacci number where F(0) = 0 and F(1) = 1.

EXAMPLES

Example 1

Input
{
  "n": 4
}

Output
3

FUNCTION SHAPE

n: int→int

SOLUTION NOTE

This is the definition of DP! Once you have the recurrence relation and base cases, the code writes itself. The hard part is discovering the correct recurrence.

Reveal reference solution +

pythonREFERENCE

def fib(self, n: int) -> int:
    @cache
    def dp(n):
        if n in [0, 1]: return n
        return dp(n-1) + dp(n-2)
    return dp(n)

TimeO(n)

SpaceO(n)

Open on LeetCode ↗