Recursion & Dynamic Programming

Question 1

Bottom-Up Approach

Answer 1

The bottom-up approach is often the most intuitive. We start with knowing how to solve the problem for a simple case, like a list with only one element. Then we figure out how to solve the problem for two elements, then for three elements, and so on. The key here is to think about how you can build the solution for one case off of the previous case (or multiple previous cases).

Question 2

Top-Down Approach

Answer 2

The top-down approach can be more complex since it’s less concrete. But sometimes, it’s the best way to think about the problem.
In these problems, we think about how we can divide the problem for case N into subproblems.

Question 3

Half-and-Half Approach

Answer 3

In addition to top-down and bottom-up approaches, it’s often effective to divide the data set in half.
For example, binary search works with a “ha!f-and-half”approach. When we look for an element in a sorted array, we first figure out which half of the array contains the value. Then we recurse and search for it in that half.
Merge sort is also a “half-and-half” approach. We sort each half of the array and then merge together the sorted halves.