pickle_juice2024's blog

What is the best way to improve on DP problems?
By pickle_juice2024, history, 14 months ago, In English

I feel like I'm extremely weak on DP problems. Can somebody suggest a way to practice DP?

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

Comments Comments (5)
| Write comment?
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I suggest reading these https://codeforces.net/blog/entry/67679 https://codeforces.net/blog/entry/80064 https://codeforces.net/blog/entry/70018

→ Reply
»
14 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Well, to get into DP, I would suggest you to do some beginner DP problem set, such as CSES, Atcoder (this one does contain some relatively hard stuff so I would suggest complete like 75% of them). Then, you would pull off the pro-gamer move in your training, which is not doing DP problem set, and just solve everything thrown at you. As counter-intuitive as it may sounds, not specifically doing DP problem will benefits you greatly, as it will train your ability to notice DP problems, as well as changing your mindset to use DP as a tool, not as the entire solution. I've met quite a few problems where DP is the easiest part lol.

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot! By the way, could you give some tips on how to reach candidate master?

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      you should get proficient at basic techniques, such at binary searching, two pointers, dynamic programming, hash and basic graph knowledge. You should also get to a certain point of math maturity. I know several people who are not that good at math, therefore it took them an excessively long time to reach Candidate Master. Some have been at Expert for like a whole 3 years.

      → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

From my experience, the best way is to just practice. It helps improve your skill and your experience to deal with problems in the future. About the problem source, I suggest the CSES problem set, it contains some nice DP problem that you can do to practice. Hope it'll help!

→ Reply