Analyze the solution

Next, we need to analyze the solution. If we look at the time complexity of our fib() function, we see that our solution will take 0(2^n). This is a very inefficient runtime.

If we want to optimize a solution using dynamic programming, it must have an optimal substructure and overlapping subproblems. We know it has overlapping subproblems because if you call fib(6), that will call fib(5) and fib(4).

fib(5) then recursively calls fib(4) and fib(3). From this, it's clear that fib(4) is being called multiple times during the execution of fib(5).

It also has an optimal substructure because we can get the right answer just by combining the result of the subproblems.

With these characteristics, we know we can use dynamic programming!