Technical implementation
Let's dig into the implementation of some of the theoretical programming techniques that we discussed previously in this chapter. We will start with dynamic programming.
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 of a pre-computed value of that subproblem previously encountered...
