Dynamic Programming Recap
At first, we started with the simplest recursive solution for Fibonacci. By using memoization, we were able to massively speed up the solution.
Why did memoization speed up the solution? It is because Fibonacci has optimal substructure and overlapping subproblems.
Optimal substructure means that the optimal solution to the problem can be created from optimal solutions of its subproblems.
In other words,
fibonacci(5) can be solved with
fibonacci(3), so the problem lends itself to a recursive solution.
Fibonacci has overlapping subproblems, as the same subproblem is called multiple times. Thus, it makes sense to use memoization to cache the results.
In addition, we looked into creating a bottom-up solution. For the recursive solution, we defined a Fibonacci number as the sum of the two previous Fibonacci numbers. However, we could start with the base cases of
fibonacci(2) and calculate the next number in the Fibonacci sequence, rather than the previous numbers in the Fibonacci sequence.