The Fibonacci numbers are defined by fib(0) = 0, fib(1) = 1 and fib(n) = fib(n-1) + fib(n-2). The definition translates directly into a recursive function, but the naive version recomputes the same values an enormous number of times: fib(60) would make more than a trillion calls.
Implement fib(n) recursively, but memoize it: remember every result you compute so that each fib(k) is calculated at most once.
Examples
Input: n = 10
Output: 55
Input: n = 1
Output: 1
Input: n = 60
Output: 1548008755920
Constraints
0 <= n <= 90- Tests must finish in well under a second, so the naive recursion will time out.
Goals
- Spot overlapping subproblems in a naive recursion
- Cache results in a dictionary so each subproblem is solved once
- Turn an exponential-time recursion into a linear-time one