Here is our pseudocode to find the -th Fibonacci number using memoization:
function fib(n):
numbers = array[0, n]
for i in [0, n]:
numbers[i] = -1
return fib_helper(n, numbers)
function fib_helper(n, numbers):
if numbers[n] != -1:
return numbers[n]
if n < 2:
numbers[n] = n
else:
numbers[n] = fib_helper(n-1, numbers) + fib_helper(n-2, numbers)
return numbers[n]
Assume that we apply the described fib function for . How many values from the numbers array will fib_helper reuse?