Who can recommend some good Dynamic Programming Problems

on this site?Thanks.

**Moderator:** Board moderators

9 posts
• Page **1** of **1**

Who can recommend some good Dynamic Programming Problems

on this site?Thanks.

on this site?Thanks.

Retired from SJTU Accelerator 2004

- hujialie
- New poster
**Posts:**43**Joined:**Thu Apr 17, 2003 10:24 am**Location:**Shanghai,China

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.

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.

- rjhadley
- Learning poster
**Posts:**73**Joined:**Mon Oct 14, 2002 7:15 am**Location:**United States

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

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

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

or

http://www.geocities.com/acmbeganer

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

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

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???

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

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.

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.

I hope you can understand my poor English.

- hiloshi
- New poster
**Posts:**20**Joined:**Fri Aug 27, 2004 8:15 am**Location:**Kanagawa, Japan

9 posts
• Page **1** of **1**

Users browsing this forum: No registered users and 0 guests