Algorithms For Dummies

Making problems dynamic

Because dynamic programming takes advantage of repeated operations, it oper-

ates well on problems that have solutions built around solving subproblems that 

the algorithm later assembles to provide a complete answer. In order to work 

effectively, a dynamic programming approach uses subproblems nested in other 

subproblems. (This approach is akin to greedy algorithms, which also require an 

optimal substructure, as explained in Chapter 15.) Only when you can break down 

a problem into nested subproblems can dynamic programming beat brute-force 

approaches that repeatedly rework the same subproblems.

As a concept, dynamic programming is a huge umbrella covering many different 

applications because it isn’t really a specific algorithm for solving a specific prob-

lem. Rather, it’s a general technique that supports problem solving.

You can trace dynamic programming to two large families of solutions: