Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

scorpi0n's blog

Need Help with Dynamic Programming
By scorpi0n, history, 10 hours ago, In English

Hello, Codeforces community! I need some help understanding dynamic programming (DP). I find it quite challenging to grasp. Could you please share some tips or recommend problems that can help me improve my DP skills? Thank you in advance!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

You can try to solve this problem set from atcoder educational dp contest. Here is the link: https://atcoder.jp/contests/dp/tasks. Best of luck!

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

    can you pls suggest something on how can i become pupil? the thing is no matter how much i try i am not able to break the newbie barrier.. i have another account where i am active and give contest but my rating is somewhat same there too. can you suggest me something please?

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

      You've gotta do math and really lock in on the problems. And don't set your expectations too high. If you try hard enough you'll be up there one day. Getting to pupil ain't that hard tbh. Expert is the real deal

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

      dont bother with 2 accounts. what is the point of lying to yourself by doing contests on an alt. also there is no secret technique that is needed for pupil. just do a bunch of A and B problems and try to solve them as fast as possible. ofcourse if you can solve C problems that would be great, but realistically you only need fast A and B for pupil

      → Reply
    • »
      »
      »
      4 hours ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      practice practice practice! solve problems of different topics especially maths, binary search... + upsolve the problems of the previous contests + fast coding (solving a,b problems fast). The way i see it is if you really want to be good at cp and put enough effort you'll surely reach a good position. Just don't lose hope and keep trying. good luck.

      → Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

dp has an omega sharp learning wall so its fine if you're struggling on it

And for me i just kept doing problems until suddenly i got past the wall

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

    And for a specific tip, do NOT visualize dp as some recursive overlapping-subproblem tree, it never worked out for me and dropping it is what got me past the wall

    My understanding of dp is: you did X? what's the result of the best way/number of ways/etc of doing that, and how could you use that to calculate Y

    → Reply