Блог пользователя siehpe

Автор siehpe, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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.