Introduction

Dynamic programming amounts to breaking down an optimization problem into simpler sub-problems, and storing the solution to each sub-problem so that each sub-problem is only solved once.

DP is a useful technique for optimization problems, those problems that seek the maximum or minimum solution given certain constraints, because it looks through all possible sub-problems and never recomputes the solution to any sub-problem. This guarantees correctness and efficiency, which we cannot say of most techniques used to solve or approximate algorithms. This alone makes DP special.

Sub-problems are smaller versions of the original problem. In fact, sub-problems often look like a reworded version of the original problem. If formulated correctly, sub-problems build on each other in order to obtain the solution to the original problem.

Those who can not remember the past are condemned to repeat it.

This dynamic program chooses between two options at each step, just like our dear friend Hamlet! [Hamlet’s Duplex]

DP is a method for solving problems by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution. This saves computation time at the expense of a (hopefully) modest expenditure in storage space.

Memoization

Memoization means no re-computation, which makes for a more efficient algorithm.

Thus, memoization ensures that dynamic programming is efficient, but it is choosing the right sub-problem that guarantees that a dynamic program goes through all possibilities in order to find the best one.

In recursive solutions, adding memoization should feel straightforward. Let’s see why. Remember that memoization is just a cache of the function results. There are times when you want to deviate from this definition in order to squeeze out some minor optimizations, but treating memoization as a function result cache is the most intuitive way to implement it.

This means that you should:

1. Store your function result into your memory before every return statement
2. Look up the memory for the function result before you start doing any other computation

Algorithm

1. Recognize a DP problem
   • Can the problem solution be expressed as a function of solutions to similar smaller problems?
2. Identify problem variables
   • Identify the changing parameters and determine the number of subproblems.
3. Clearly express the recurrence relation
   • Assuming you have computed the subproblems, how would you compute the main problem?
4. Identify the base cases
5. Decide if you want to implement it iteratively or recursively