Sourabh-Choudhary's blog

How to improve my DP ??
By Sourabh-Choudhary, history, 3 years 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

Comments Comments (14)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When should we start doing dp ?

→ Reply
»
3 years 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.

→ Reply
»
3 years 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

→ Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Now i'm curious

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 years 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

→ Reply
»
3 years 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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Dp everyday!

→ Reply