What is Dynamic Programming??
Posted: Sun Jun 02, 2002 4:02 pm
As topic. As topic.Page 1 of 1
As topic.Posted: 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.
Dynamic Programming
Posted: 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
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
Posted: 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.
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.
Posted: 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 