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.
Thank you very much my friend! I shall start solving dp problems of rating 1000 and slowly increase, and I will follow your technique! Thanks <3
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 !
I think that is my problem.. I always try iterative methods. Thanks a million for your help :) Thanks for the motivation!! I'll get started as soon as I can. :)
You can take a look at this.I think my answer will help you.
Do more DP problems and understand this, I studied only DP for 4 months and now, I think I'm good at DP. First, DP[][]... is save all states u need. After that, if u do can do this, let's find some states u don't need and remove them from DP, optimal and optimal, so u can do DP (if u optimize all but can't solve this, don't worry, let's read Editorial, u will become better than in DP). This is my advice for u. (My English is not good hihi).
thanksss :)
To linking the sub-problem part , I would say just imagine you have solution of sub-problem and our task is just to find the solution of next bigger-problem and then try. I know I just stated the obvious but that's how I try to approach. And of course practice is the way, so check these https://blog.shahjalalshohag.com/topic-list/ , its given by YouKn0wWho. (Idk how to tag :p) there was a blog a I saw last month which had 100 must solve problem ,can't find it right now if someone else can give link. I am also not a pro so let's keep up the grind .
thanks for the resource :)
I think at this stage you don't need to learn Dynamic Programming, you should have a strong grip on some small topics such as Prefix array, Binary Search on Answer, Two Pointers,some Number Theory concepts such as Sieve of Eratosthenes,Factorization of a number and many more. You can refer to the Edu Section of codefoces and cp-algorithm. Once you have reached till 1400 rated then you can study DP but at this time you will not get a DP problem at question B in div.2 and you will get demotivated.
DP is hard for beginners, easy for experts. DP is the easiest topic in high level problems, aside from Segment Trees
I know.. its hard to make that transition and I hope I can do it soon.
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 think you should practice dp from leetcode. You can practice the neetcode.io list of dp section and try to solve the problems by yourself no matter what. See, it's all about confidence. I solved the burst balloons dp problem by myself in 4 days. But the effort and time taken was worth it and it gave me a lot of confidence in dp problems.
I'm pretty sure dp is ez.
YES sumit_ag2002
From last few days, I am also figuring out how to improve this thinking process regarding dp states. Like in this question, I literally have not any clue how to achieve this kind of solution.
Currently I am following this list to improve my dp. It might help you.
If any suggestions from anyone, most welcome.
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.