I don't understand Dynamic Programming

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Kaul
New poster
Posts: 4
Joined: Tue May 02, 2006 10:56 am
Location: Seoul, Korea
Contact:

I don't understand Dynamic Programming

Post by Kaul »

I'm studying DP, but I can't get it :(

I read the book to study Dynamic Programming, but I can't get it.

I know that DP uses arrays much, but I can't divide the main problem to subproblems.

Please help me!

* Sorry about my bad English :roll:
______Have a Nice Day :)______
Dokdo is the Korean territory!

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha »

The best way to learn DP, write and think about some well-known DP problem.

I recommand you to write Knapsack and coin problem.
Just Keep on thinking....

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll »

Here's a tutorial on dynamic programming:

http://www.topcoder.com/tc?module=Stati ... d2=dynProg

Here's another website with lots of source code examples and links to problems which use the algorithms:

http://www.comp.nus.edu.sg/~stevenha/pr ... mming.html

Reading about DP is good, but it's better to try some of the easier DP problems (some of these problems can be tricky because they require that the path must be output as well):

674 (coin change)
348 (matrix multiplication)
231 (longest increasing subsequence)
10066 (longest common subsequence)
164 (edit distance)
507 (maximum interval sum, 1D)
108 (maximum rectangle sum, 2D, has both n^4 and n^3 algorithms)
431 (0-1 knapsack)
10130 (0-1 knapsack, multiple sacks)
10359 (tiling, very instructive example of an easy recurrence that can be converted to a dynamic programming solution)

Topcoder TCO2005 Round 1 FibonacciSum (represent n using fewest additions) (sorry, I couldn't find a similar problem on UVa)
Topcoder TCCC2005 Round 1 ChessKnight (find probabilities on a chessboard)

Some slightly harder problems where DP can be used:

10157 (a good exercise in trying to define the state)
10827 (harder version of 108)
10835
10888
10918 (harder version of 10359)
11008
11022

Kaul
New poster
Posts: 4
Joined: Tue May 02, 2006 10:56 am
Location: Seoul, Korea
Contact:

Thanks, Moha & stubbscroll!

Post by Kaul »

Thank you for many many suggestions! I'm keep studying about DP.

The examples were very useful, and I'm trying to solve the easy DP problems.

Thank you again!
______Have a Nice Day :)______
Dokdo is the Korean territory!

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse »

yeah, I'm a newbie to DP as well. The shortest path and string editing problems we did in class looked easy. Then when I tried some of these acm problems, I'm having a hard time.


I can definitely see how 674 - coin change problem is dynamic programming, but I don't see the relationship between coins. I guess I'm having trouble coming up with a relationship to build my table.

The stuff we did in class basically builds the table from small pieces and use them in building large pieces -- another words, bottom up approach. The coin change problem is a bottom up problem, but I can't find the relationship to build it upon.

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal »

For proble 674-Coin Change, I tried to find a DP solution, but could not find the recurrence relation after thinking for a long time. Finally I solved it by multiplying five polynomials. Can anyone show me the recurrence relation for this problem ?

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse »

yeah, I can show it to you. I finally figured it out with the help of another member of the forum. But you have to be patient though. I'm kinda busy right now, and I can only put down an explanation during hte weekends. It might not even be this weekend.

The thing is, you have to draw the actual table to figure out the relationship. And if you don't know the relationship, you can't draw the table. So, to show you how it works, I'll have to draw the table for you, and tell you how I built it. That takes time, and since I solved it a while back, it's not really fresh in my head, but I have no doubt that I can reconstruct the table easily.


ttyl

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal »

Its OK, no problem, I have found the relation and got AC with DP solution as well. Thanks anyways.

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse »

cool. Hey, are you really interested in DP? I'm a beginner as well. The coin change problem, I think, was the first DP problem I've solved. I also found another DP problem that is interesting. It's 10003 -- Cutting Sticks. I believe I found the solution for that one as well. I'm going to code it up this weekend and submit it.


Are you going to solve a bunch of DP problems too?

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal »

Are you going to solve a bunch of DP problems too?
I would be glad to :)

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal »

Those who have solved 674 can consider trying 147 too.

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse »

those are nice problems. The 147 one is pretty much the same as the coin change problem.

Post Reply

Return to “Algorithms”