Introducing Dynamic Programming with Fibonacci Numbers

We are now going to use a dynamic programming technique to reduce the time complexity to linear.

What is dynamic programming?

Dynamic programming algorithms solve problems by combining the results of subproblems, just like in divide-and-conquer algorithms.

Characteristics

Most problems that can be solved with dynamic programming can also be solved with a divide-and-conquer approach. The difference between the two is that the dynamic programming approach is applicable when a problem has overlapping subproblems; i.e., the subproblems of a given problem are not independent, such as when two subproblems share a sub-subproblem. An example would be the Fibonacci code we saw in the last lesson where fib(3) had to be calculated in order to calculate both fib(4) and fib(5).

Furthermore, dynamic programming problems have the optimal substructure property, which means that the overall optimal solution of the problem can be constructed from the optimal solutions of its subproblems. For Fibonacci numbers, we know that

fib(n) = fib(n-1) + fib(n-2)

Therefore, a problem of size $n$ can be reduced to subproblems of size $n-1$ and $n-2$. Therefore, Fibonacci numbers have the optimal substructure property.

Dynamic programming algorithms solve every subproblem just once and save the answer in a lookup table, thereby avoiding recalculating the answer every time the subproblem is encountered.

There are two dynamic programming patterns: memoization and tabulation.

Memoization (top-down)

The memoized version (yes, that is not a typo - it’s memoization, not memorization) of a problem is similar to the regular recursive version; the difference is that it looks for the answer of a subproblem in a lookup table before computing its solution. If the precomputed value exists, then it is returned. Otherwise, the value is computed and put in the lookup table so that it can be reused later.