Next: Fibonacci numbers Up: Breaking Problems Down Previous: Breaking Problems Down

# Dynamic Programming

After you understand it, dynamic programming is probably the easiest algorithm design technique to apply in practice. In fact, I find that dynamic programming algorithms are usually easier to reinvent than to try to look up in a book. Until you understand it, however, dynamic programming seems like magic. You have to figure out the trick before you can use it.

In algorithms for problems such as sorting, correctness tends to be easier to verify than efficiency. This is not the case for optimization problems, where we seek to find a solution that maximizes or minimizes some function. In designing algorithms for an optimization problem, we must prove that our algorithm always gives the best possible solution.

Greedy algorithms, which make the best local decision at each step, occasionally happen to produce a global optimum for certain problems. These are typically efficient. However, you need a proof to show that you always end up with the best answer. Exhaustive search algorithms, which try all possibilities and select the best, by definition must always produce the optimum result, but usually at a prohibitive cost in terms of time complexity.

Dynamic programming combines the best of both worlds. The technique systematically considers all possible decisions and always selects the one that proves to be the best. By storing the consequences of all possible decisions to date and using this information in a systematic way, the total amount of work is minimized. Dynamic programming is best learned by carefully studying a number of examples until things start to click.

Algorithms
Mon Jun 2 23:33:50 EDT 1997