I don't understand Dynamic Programming
Moderator: Board moderators
I don't understand Dynamic Programming
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
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
______Have a Nice Day ______
Dokdo is the Korean territory!
Dokdo is the Korean territory!

 Experienced poster
 Posts: 151
 Joined: Tue Nov 16, 2004 7:23 pm
 Location: Norway
 Contact:
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 (01 knapsack)
10130 (01 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
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 (01 knapsack)
10130 (01 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
Thanks, Moha & stubbscroll!
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!
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!
Dokdo is the Korean territory!
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.
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.

 Experienced poster
 Posts: 106
 Joined: Thu Jan 29, 2004 12:07 pm
 Location: Bangladesh
 Contact:
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
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

 Experienced poster
 Posts: 106
 Joined: Thu Jan 29, 2004 12:07 pm
 Location: Bangladesh
 Contact:
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?

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

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