Dynamic Programming Problems

Let's talk about algorithms!

Moderator: Board moderators

Dynamic Programming Problems

by hujialie » Tue Oct 14, 2003 4:37 pm

Who can recommend some good Dynamic Programming Problems
on this site?Thanks.
Retired from SJTU Accelerator 2004
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

by rjhadley » Tue Oct 14, 2003 10:50 pm

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.
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

by gvcormac » Sun Oct 19, 2003 9:51 pm

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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am

by hujialie » Wed Oct 29, 2003 3:28 pm

Thank you all for your reply.
I will try to solve them. :P
Retired from SJTU Accelerator 2004
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

by Master » Wed Feb 25, 2004 10:51 am

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


Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada

by anupam » Wed Feb 25, 2004 8:55 pm

As far as i can think,
there is another beautiful problem named
"hour glass" in the vol-105.
try this.
"Everything should be made simple, but not always simpler"
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm

by Duy Hung » Fri Mar 12, 2004 6:38 am

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???
Duy Hung
New poster
Posts: 7
Joined: Sat Jan 17, 2004 3:50 pm
Location: Viet Nam

by hiloshi » Sun Aug 29, 2004 2:37 pm

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.

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.
I hope you can understand my poor English.
New poster
Posts: 20
Joined: Fri Aug 27, 2004 8:15 am
Location: Kanagawa, Japan

by sclo » Fri Feb 10, 2006 8:33 am

The old regionals are full of DP problems too
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada

Return to Algorithms

Who is online

Users browsing this forum: No registered users and 1 guest