siehpe's blog

By siehpe, history, 8 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

| Write comment?
»
8 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.