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.

- Fibonacci numbers
- The Partition Problem
- Approximate String Matching
- Longest Increasing Sequence
- Minimum Weight Triangulation

Mon Jun 2 23:33:50 EDT 1997