About Dynamic Programming

[lyjgeorge]

Hello,everybody!
I'm a newcomer to this forum.
I think that Dynamic Programming is quite an important way to solve OI problems. But it seems a bit difficult to learn.
So I want someone to paste some MODEL problem for using Dynamic Programming.....

Thank you . I want to improve both my skill on algorithm and my English

[Miguel Angel]

Well, I think that DP is a very(VERY) general approach, which must meet the following conditions:
(Let A and B two distinct events)
* A and B must be independent events (that is, changes on A doesn't affect changes on B)
* There's exist some precedence or order between A and B
And the most important:
* The optimum of every event can be calculated from the optimum of their ancestors.

There'r many many problems about DP, involving: Graphs, Maths, finite NP problems, and Trivial problems. Almost can be modeled mathematically, u can develop ur ability on DP just doing those problems .

[lyjgeorge]

Why reply needs Subject?

[lyjgeorge]

Well,Miguel Angel
Would you please introduce some problems at this site which should use Dynamic Programming(Just simple DP) to solve ?

I want to do some simple DP now.


After that I'll find some difficult problem to solve.

[Ming Han]

Hi,

I think ACM 108 is a DP problem... not sure.

anyway, http://www.comp.nus.edu.sg/~stevenha/pr ... g_dp1.html is a very good site on DP.

Ming Han

[Juergen Werner]

Here you can find an assigment of some online judge problems to several categories (including DP): http://www.cs.sunysb.edu/~skiena/390/hw.html

There are a lot more DP problems on the site (like 531 Compromise), but the ones listed by the link above should do for the beginning.