Блог пользователя Sourabh-Choudhary

Автор Sourabh-Choudhary, история, 3 года назад, По-английски

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.

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When should we start doing dp ?

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

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.

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

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

»
3 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

if nobody needs i won't type them again.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Now i'm curious

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      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.

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Dp everyday!