OJ Board

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

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

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

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!

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.

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 ?

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

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

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?

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

I would be glad to

Those who have solved 674 can consider trying 147 too.

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