siehpe's blog

By siehpe, history, 4 years ago, In English,

Hello everyone,
I have been solving competitive programming problems for about a year (on other online judges). I have learnt various standard algorithms like bfs/dfs, bitmask technique etc and I feel I have made reasonable progress in those topics and can solve easy — medium problems of those topics. However the same is not true for dynamic programming.

I must have solved over a hundred dynamic programming problems, yet when I see a new one I have no idea how to solve it. I feel as if each problem is completely different from the other. Also I cannot see any pattern in their solutions like I see for problems related to other standard techniques. I would appreciate it if anyone could guide my on how to go about solving dp problems, a proper methodical approach . Please do say something like "practice makes perfect" because I have solved a lot of problems yet not made any progress.

Im hoping to get lots of responses cause I know there are many dp experts out there.

Thank You

 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Well, I'm surely not a "dp expert", but here you are my piece of advice: find a way to describe the state unambiguously, and then find how to recalculate it using previous states. And never forget to use protection recursion.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your reply :) , but what I wanted to know was how to train in this topic.It would help if you could give me any links which you used to learn dp (beginner to advanced) and some corresponding problems related to the theory in the given links.