I don't understand Dynamic Programming

Kaul · Post by **Kaul** » Wed May 03, 2006 10:42 am

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

Moha · Post by **Moha** » Thu May 04, 2006 1:42 pm

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 · Post by **stubbscroll** » Fri May 05, 2006 6:08 pm

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 · Post by **Kaul** » Sat May 06, 2006 9:04 am

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!

jjtse · Post by **jjtse** » Sat May 13, 2006 3:17 am

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 · Post by **Raiyan Kamal** » Thu Jul 13, 2006 10:56 am

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 · Post by **jjtse** » Thu Jul 13, 2006 11:23 pm

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 · Post by **Raiyan Kamal** » Fri Jul 14, 2006 6:39 am

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

jjtse · Post by **jjtse** » Fri Jul 14, 2006 8:02 am

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 · Post by **Raiyan Kamal** » Fri Jul 14, 2006 4:45 pm

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

I would be glad to

Raiyan Kamal · Post by **Raiyan Kamal** » Fri Jul 14, 2006 5:22 pm

Those who have solved 674 can consider trying 147 too.

jjtse · Post by **jjtse** » Fri Jul 14, 2006 8:32 pm

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

OJ Board

I don't understand Dynamic Programming

I don't understand Dynamic Programming

Thanks, Moha & stubbscroll!