Fibonacci(n)

Memoisation beats naive recursion.

recursion dp memoization

Implement `fib(n: int) -> int`.

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2).
Must run in better than O(2^n) time.

Constraints

0 ≤ n ≤ 50

Example

>>> fib(10)
55

15 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a loop to track prev/curr, or use functools.lru_cache.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.