Re: Dynamic Programming I found some more interesting things about dynamic programming that I
would like to add to Mike's message. They are from the book
"Intorduction to Algorithms" by Cormen, Leiserson, Rivest (The MIT Press,
McGraw-Hill Book Company, 1990):

""Programming" in this context refers to a tabular method, not to writing
computer code.... Divide-and-conquer algorithms partition the problem into
independent subproblems, solve the subproblems recursively, and then
combine their solutions to solve the original problem. In contrast,
dynamic programming is applicable when the subproblems are not
independent, that is, when subproblems share subsubproblems. In this
context a divide-and-conquer algorithm does more work than necessary,
repeatedly solving the common subsubproblems. A dynamic-programming
algorithm solves every subsubproblem just once and then saves its answer
in a table..."

This first made me more confused than before. But when I thought of a
combinatorial problem (like the one we did in class), and tried to apply
the normal divide-and-conquer method to it, I realized how dyn.prog. would
work in it but div-n-conq would fail.

Dynamic programming rules :)

Amar

