In this chapter, we are going to learn Dynamic Programming. The gist of Dynamic Programming is to solve the overlapping subproblems, cache the results, and reuse these results to find a solution. This is different from the divide-and-conquer introduced in Chapter 2 which divides the problem into a series of individual and nonoverlapping subproblems. Dynamic Programming utilizes the idea of recursion in Chapter 1 and caches the intermediate results. It can be used to find the optimal solution for certain problems where the Greedy Algorithm in Chapter 3 can only find an approximate solution. In the chapter, we use a “bottom-up” approach to cache the results by storing them in a one-dimensional table or multidimensional tables. Let us get started!