Sourabh112's blog

By Sourabh112, history, 5 weeks ago, In English

Hi, Codeforces community,

I'm trying to improve my Dynamic programming. I'm able to solve DP problems under 1100-1200 but struggle with DP problems above that rating (When I don't know I have to use DP). The major problem I'm having and which I want to ask with the help of this blog is how to practice to improve?

When I practice DP by searching DP problems specifically by tags I simply don't see improvement because I know I have to apply DP. And came to the conclusion that I can solve the DP problem but just don't know when to use DP. So, How should I practice to improve this? I know Practice is the solution but guidance on how Should I practice would be helpful.

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When should we start doing dp ?

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Star random DP and non-DP problems without seeing the problem name.

Solve them from favorites, now you won't know if it's a DP problem or not.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Practice. Do approx 500 problems on Dp and then you are good to go.
Beginner:Click me
Medium: Click me
Hard: Click me

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    500 seems like an incredibly inefficient practice routine

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It just a random number that came to my mind, you can even try 499 problems XD.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What a coincidence I actually started the beginner's one this morning. Thanks for the advice.

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

i'm crying loudly because bad connect made me lose what i had typed !!!

if nobody needs i won't type them again.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Now i'm curious

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      emm……i try to write down some of my thoughts.it's not easy because of my poor English.

      i think it's necessary to do some exercise.but not too much.for each problem,try to solve it by yourself at first.maybe it's hard to solve but don't worry.to see the solution,just like what i always do XD.don't just copy the answer like dp[i][j] = dp[i-1][j] + (n-i)*dp[i-1][j-1].try to find out how it works,and why it is correct.

      to learn about what is the meaning of 'dp' and the meaning of state transition equation.this is IMPORTANT.

      P.S i don't know how to describe 'state transition equation' in English ,maybe it's incorrect.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Perhaps Aditya Verma Dp playlist can help you to learn concept in very clear and structured way. He explain how to find that dp is applied in some question or not. Link

For rest I can say that it comes with your experience. Explore more question (of different types) on other's platform too.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Honestly, Aditya Verma DP playlist is way too fkn underrated, people need to know about it more, especially beginners, it's all in Hindi so I guess non-hindi speakers won't get it.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Practice randomly :p

Dis way, you don't have context for the dp problem and the solutions will be less obvious, meaning that you'll probably learn a lot more from doing that problem over another dp problem.

If it's hard to see improvement fast check out the greedy and dp tags. Here you'll maybe gain more intuition for dp and possibly learn how to solve problems with both.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

https://cses.fi/problemset/ just do all DP problems.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Step 1: Start with a little on Day-1, basically an easy problem,

Step 2: The next day, build up upon what you learned the previous day.

Step 3: Repeat Step 2

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'll tell you what helped me, try and understand all the standard DP problems, be it knapsack or coin change, do cses dp section. After that start doing cf, you'll feel better about it.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Dp everyday!

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

Ig cses(dp) and leetcode(dp section) are really the best places to start dp from. They have trivial dp problems which can help you improve your "raw" dp skill.

Then learn some new tricks like bitmasking, range dp, matching dp etc.

Now solve every problem on dp on USACO Guide (Gold/Platinum).

Then solve every problem on Atcoder dp contest(It even has a editorial now Lunchbox orz).

Then finally move onto CF dp section 1600+ only. You can also use binarysearch.com for additional dp practice. If you feel like it.