eclips's blog

Searching a way to solve DP & Recursion...........
By eclips, 13 years ago, In English
I know the basic idea of DP & recursion. But it takes to many times to solve a simple DP.How can I become skilled in DP & Recursion ? Is there any basic idea which help me to catch the type of problem & help to find the correct approach?

Thanks in advance....
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
You can try reading CLRS' chapter on Dynamic Programming. Gives basic idea of questions approachable by DP.
As for the method itself, I guess once you know its a DP prob, you just have to find the sub structure
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Same here.  Writing recurrences down to paper explicitly worked for me a bit.  If you're more familiar to recursion than to DP, you could start with memoized recursion, because they're equivalent when you have enough space for memoization and don't have to reuse it.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Introduction to Algorithms by Thomas H. Cormen .This book has very nice discussion on Dynamic programming .I found it really important...
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
To catch the type of problem you should have solved some related problems before. For DP TopCoder Div-2 500pt DP problems are relatively easy and good for start. After this try Div-1 250pt DP problems (Some of them are hard!). I proposed TopCoder problems because they have complete editorial (In case you couldn't solve the problem or even after solving it).Try to solve problems that you have solved with memoization, without it. After these you are ready to challenge yourself with problems on this post. Having solved all these problems, you can apply DP on related problems easily!
→ Reply