Hello there, I am having hard time dealing with dp problems can you help me get started with them

To put you into perspective I am not able to even recognize the problem type, I am somewhat confident in graph theory and number theory problems but dynamic programming just seems too difficult, any suggestions of where I could get started with it also the main problem I’m facing with it is I’m unable to understand why dp is even needed( of course I am at fault and part of the reason is why I’m asking you this ) and just could not anticipate it’s use case.

2 Likes

Hey there @pawan_31. I am learning DP too.
I would suggest you to try these out too.

1.Tushar Roy DP tutorial
2. Rachit Jain’s Dp tutorial(could be bit overwhelming)
3. At coder Educational DP Contest
4. This great blog post
5. Codeforces problem set(try them out in ascending order of diffficulty)

Hope it helps.
Cheers.

1 Like

The best thing to get you started is the chapter on CLRS in my opinion. After that, binge-solve as many classical problems (and their variations) as you can. Proceed to other tutorials on the way: the wine problem answer on Quora, TopCoder, Algorithms Live, Codeforces blogs on the topic, to name a few. Give a week or two to the topic in this fashion and you’ll feel start feeling comfortable with the problems. Also, most guys will suggest the AtCoder DP contest which is great by the way (but you need more than just a week or two practice to finish that exhaustively). I hope you start seeing the patterns with enough practice. One more thing: don’t ask anymore and start practicing!

1 Like

I also struggled (and still struggle) with DP. But what helped me understand it better was - “look at DP problems as recursion problems i.e. Make recursive solution first and then the actual DP part is just optimizing it by storing the repeated work”. This is the top-down approach and this helped me the most.
Once you get this by lots of practice, the bottom-up(tabulation) will come naturally to you.

Now, if you are week at recursion you will be week at DP. Thus try recursive problems first, if you are week at them. A great resource for recursion -

  1. ByteByByte Recursion

If you feel confident about making recursive solutions, then some great resources for top-down DP are -

  1. Aditya Verma DP tutorial
  2. Back to Back SWE DP solution videos
  3. Doc 1
  4. Doc 2
  5. Doc 3
  6. Doc 4
1 Like

Problem Set: https://cses.fi/problemset/list
Solution for DP problems: https://codeforces.com/blog/entry/70018

After this, you could approach hacker-rank dp problems. Just because those problems are solved by many people so it will be easy to find tutorials online.

Aditya Verma is okay, he keeps repeating, half of his video has no value. it feels like he is spoon feeding. i got vexed even though i watched it in 2x

I guess for beginner it is good .

Take a look here @pawan_31 Data Structures and Algorithms

yaa you are right. The videos were too long but as a beginner I found them helpful that’s why I suggested them.

Can you share links to more Atcoder educational contests?

I do not practice at Atcoder, but I think the Educational DP contest is the most famous out there.
This was especially made for DP, there might not be for other topics if you are looking for them.

1 Like