pickle_juice2024's blog

What is the best way to improve on DP problems?
By pickle_juice2024, history, 18 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 (8)
| Write comment?
»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

Try to solve DP problems using tabulation method and first of all try to understand 0-1 knapsack. Tabulation method will provide you a more clear understanding how dp actually works

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

    I know how DP works, but I just can't figure out how to use DP in problems.

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

      For solving DP problems try to form a state for the problems and try to see how to change from one state to another. For forming a state try to minimise the problem, like for forming Fibonacci series try to see how fib(4) could be formed from fib(3) and for changing the state see what changes are being done for getting fib(4) from fib(3)

      → Reply
»
18 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
  • »
    »
    18 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
    • »
      »
      »
      18 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
»
18 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