Hello Codeforces! I've recently been trying to learn the dynamic programming approach, and I might've had some success, but it is still really hard for me to think of defining a "state" for the problem. Even after the thought of the state, it is hard to link the states to previous sub-states. I find it hard to approach dp problems in general, and I just need some advice on how to practice in order to improve my dp approach. If you could guide me a little, I would love it <3 !. Not only high-rated persons, everyone who knows something about dp can help me. (P.S. Dont judge my profile I give contests on mostly atcoder where I am about to become Green)
I don't need upvotes, I want to improve :)
than you will take more upvote :D
I cant give you advice other than solving easy dp problems. maybe check editorials for first problems but try to do other ones on your own. dp can be very hard for some problems no matter how much you improve in it you can never say you can solve any dp problem xD
Thanks a lot friend! :) Do you remember some easy problems that you solved during your journey?
Check Atcoder DP contest. It has many good DP problems. CSES is good too
hmm why not try problem C from previous contest
I wouldn't call that an easy DP problem for someone just starting out with DP.
to be honest it was really easy if you knew it was dp. however for 30 minutes i never thought about dp. it just didnt look like a dp
Well yeah, probably. I also didn't think about dp for a long time on that problem.
I feel guilty whenever I read an editorial. It feels like I don't deserve that submission.
After you've tried solving the problem without help, if you can't come up with anything, start reading the editorial. But don't read it completely — stop when you realize something new. Try to solve the rest of the problem on your own. If you still can't come up with anything, continue reading. Keep doing this until you solve the problem or have to read the editorial completely.
After the problem, try to think how you could've come up with the answer yourself. Try to find out if there was some key observation you were missing or were you just thinking about the problem in a wrong way, for example.
As I can remember, DP was the hardest topic for me to understand, so it's alright don't give up!
For the advice, always think about the slow recursion solution and try to optimize it with memoization (it's much easier for you to think about while you're still not that good in dp than iterative dp).
Goodluck !
DP is hard for beginners, easy for experts. DP is the easiest topic in high level problems, aside from Segment Trees
This blog offers most of the places that have good dp material. Dynamic Programming is mostly about practice, so once you do enough easy problems, you should get used to the idea. Don't worry about not being able to do a certain problem that could be solved with dp even after you trained a lot, dp is a very broad topic, that is complex even to the most competent.
I'm pretty sure dp is ez.
freeCodeCamp blog on basics of DP
Errichto's DP Playlist
Educational DP Contest
The above resources should be enough to get you prepared up to a decent level. Disclaimer — if you don't understand any part of the video, pause, rewind, go over it again, do this a few times until you find clarity, that should help.
Additionally, some vague advice, but this is what I normally do, look at the extremes, the base case generally lies somewhere along those lines, smallest value? largest value? left most? right most? taking all? taking none/one?
Try to think of a reasonable set of values that can define a particular state, can you go with dp[i][j] where i, and, j, are some properties of the problem? Try to think of such properties, once you're confident that you have a fair set of properties, don't worry about the time complexity just yet, more often than not, you'll be taking unnecessary ones on top at the start, but go ahead, think of the transitions between states, how does dp[i][j] relate to dp[i][j+1] or dp[i+1][j] or some other state, define this, once that's done, you should be able to get a better picture, now try to optimize away the set of values you included in states, is dp[i][j] needed really? can you do the work with just dp[i] or dp[j], think along these lines and you should be able to get to the required states.
If you have read this far, my last piece of advice would be to solve questions from the contest that I've linked. Try to solve problems both iteratively and recursively. Some problems seem easier one way, while some are easier the other way. It's best to have a grasp of both. Additionally, the problems in the contest are foundational. While you don't need to solve all of them to become good at DP, solving a few should give you a good base to work with.
Thank you so much friend:). As of now I was fighting one of the dp problems from atcoder. Thanks for making things clear.