How do you compute Fibonacci with dynamic programming, and what does it save you?
You remember the answers that you have already worked out, so that the same Fibonacci number is never calculated twice.
def fib_memo(n, memo):
if n < 2:
return n
if n not in memo:
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
So what does it save you? It turns an exponential algorithm into a linear one. The naive recursion calls the same number over and over, and the number of calls grows like the number itself grows.
the number the naive calls the calls with a memo
------------ ---------------- -------------------
10 177 10
20 21,827 20
30 2,692,605 30
40 331 million 40
And the reason the naive version is so bad is that it does the same work twice. The answer for n is the answer for n minus one plus the answer for n minus two. So the answer for n minus one is worked out once for the left side and once again for the right side of the same calculation, and then all of that is repeated for the numbers below.
And the fix is the dictionary. The key is the number itself, because the answer for n only depends on n. And the base case is if n < 2, which gives back zero for n of zero and one for n of one.
the call the answer the memo after
-------------- ----------- ------------------------
fib(4) 3 {(4): 3}
fib(3) 2 and (3): 2
fib(2) 1 and (2): 1
And the complexity is O of n for the time, because each number is worked out once, and O of n for the space for the dictionary plus the call stack.
And there is a detail worth knowing about. The Fibonacci numbers get very big very fast. The number for n of a hundred has about twenty digits, so the arithmetic is not constant time for big numbers. In most interviews the complexity is counted as if adding numbers was constant.
So the rule to remember is this. The memo saves the repeated work, and the growth goes from exponential to linear.
The last question in this topic shows the version with no memory at all.