Dynamic Programming Problems

[hujialie]

Who can recommend some good Dynamic Programming Problems
on this site?Thanks.

[rjhadley]

Some problems which can be solved using dynamic programming are:

111: History Grading
147: Dollars
231: Testing the CATCHER
348: Optimal Array Multiplication Sequence
357: Let Me Count The Ways
497: Strategic Defense Initiative
562: Dividing Coins
674: Coin Change
711: Dividing Up
10032: Tug Of War
10081: Tight Words
10304 Optimal Binary Search Tree
10405: Longest Common Subsequence
10465: Homer Simpson
10482: The Candyman Can
10549: Russian Dolls
10558: A Brief Gerrymander

348, 10405, and 562/674 are fairly classic DP problems - at least one, if not all of them, will probably appear in any text that discusses DP. So one of these might be a good starting point. If you're looking for something which isn't quite as straightforward, perhaps try something like 497 or 10032. More challenging ones are 10304, 10549, 10558.

[gvcormac]

Here are some more problems that can be solved with DP:

10131 Is Bigger Smarter?
10201 Advantures in Moving Part IV
10254 Weights and Measures
10259 Hippity Hopscotch
10261 Ferry Loading
10280 Old Wine into New Bottles
10379 Pit Stop Strategy
10400 Game Show Math
10529 Dumb Bones

[hujialie]

Thank you all for your reply.
I will try to solve them.

[Master]

Aother very interesting dynamic problem is 116.

you can find a list of dynamic problems and many other subject oriented problem list on the site http://www.acmbeginner.tk

or

http://www.geocities.com/acmbeganer

[anupam]

As far as i can think,
there is another beautiful problem named
"hour glass" in the vol-105.
try this.
--
Anupam

[Duy Hung]

Sorry, but those webs are not available !
I'm trying to solve all those problems, and I have done about 60%. Those remains are very difficult to me... so I want to do more problem easier than them. Can anyone help me???

[hiloshi]

hi friends.

I began to try to solve some DP problems, too.
And I got AC some problems.

Problems that I was able to get the correct answer easily are follows.
103
10069
10405

I think 103 is the most simple DP problem.
And 10069 is same as above.
But to solve this prolme needs BigNumber. You should use your library for BigNumber.
If you use matrix for 10069, you will get (or maybe not) MemoryLimitExceed, so you have to use array.
And the problem 10405 is not easy to solve for me.
But I got understand LCS, problem became easy. This problem is a simple LCS problem.

If I can find other easy DP problems, I will post replay.

[sclo]

The old regionals are full of DP problems too