What is Dynamic Programming??

Melon Melon · Post by **Melon Melon** » Sun Jun 02, 2002 4:02 pm

As topic.

Stefan Pochmann · Post by **Stefan Pochmann** » Sun Jun 02, 2002 11:29 pm

It's a general, very useful technique. You'll find it in every good general algorithm book, for example Skiena or CLRS. It exploits optimal substructure and overlapping subproblems of problems and usually involves having a large table of answers for subproblems so that they're computed only once and in subsequent request just looked up in the table.

Ming Han · Post by **Ming Han** » Mon Jun 10, 2002 6:03 am

Dynamic Programming

Definition: An algorithmic technique in which an optimization problem is solved by caching subproblem solutions (memoization) rather than recomputing them.

see http://www.nist.gov/dads/HTML/dynamicprog.html

Stefan Pochmann · Post by **Stefan Pochmann** » Mon Jun 10, 2002 10:05 am

Hmm, I'm not sure if I'd accept that as a "definition". One thing that both you and I missed is that it's not only applied to optimization problems. Or is it only called DP when it is? Hmm...

Btw, has anybody read the book by Bellman and understood it? I looked into it once, but didn't get too far. It's pretty abstract, I think.

Moebius · Post by **Moebius** » Sat Nov 02, 2002 1:50 am

Conclusion: it's just the ancient technique of making tables of precomputed values, but with a nifty name