Top Down and Bottom Up Approaches

Solution

In the previous section, we discussed a recursive solution with exponential complexity. Now we'll look at two ways to solve the same problem, first using the DP top-down approach and then the DP bottom-up approach.

We saw in the recursive solution that subproblems are solved over and over again. We can store the solutions of the subproblems and avoid calculating them repeatedly. This is called memoization, where the algorithm remembers solutions to previously computed problems.

The only change required to make our recursive algorithm polynomial is to start storing the solutions to the subproblems; the necessary code appears below.