Python Data Structures and Algorithms

Dynamic programming

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

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

A property of a problem that will make it an ideal candidate for being solved with dynamic programming is that it should have 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 the result ...