Select topics to narrow your question pool, then enable Random to jump to a random question matching your filters.

Python Quiz #48

Remembering Subproblems

mediumData Structures & Algorithms

The naive recursive fib(35) takes seconds because it computes the same values again and again. What does memoisation change, as in the version below?

📄 Code

1memo: dict[int, int] = {}
2 
3 
4def fib(n: int) -> int:
5    if n < 2:
6        return n
7    if n in memo:
8        return memo[n]
9    memo[n] = fib(n - 1) + fib(n - 2)
10    return memo[n]
11 
12 
13print(fib(90))