As we have already described, in this approach, we divide a given problem into smaller subproblems. In finding the solution, care is taken not to recompute any of the previously encountered subproblems.

This sounds a bit like recursion, but things are a little different here. A problem may lend itself to being solved by using dynamic programming, but will not necessarily take the form of making recursive calls.

One property that makes a problem an ideal candidate for being solved with dynamic programming is that it has an overlapping set of subproblems.

Once we realize that the form of subproblems has repeated itself during computation, we need not compute it again. Instead, we return a pre-computed result for that previously encountered subproblem.

To ensure that we never have to re-evaluate a subproblem, we need an efficient way to store the results of each subproblem. The following two techniques are readily available.