Yeah,the common answer would be "PRACTICE". I face some problems practicing DP problems.I barely can upsolve <= 1800 rated DP problems. I can identify DP problems but cannot really make way to solve it in contest time. The most common problem I face is to "FINDING THE STATES". Moreover,I feel very uncomfortable with iterative DP approach. As maximum DP solutions are solved in iterative way,it becomes very hard for me to get them. I'm seeking some suggestions to be a good DP problem solver.
Sorry for my poor English :(
For Hindi Audience, I found these as very good Dp Resources.
Youtube
Youtube
Practice
I first learned DP here: https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns
If you are uncomfortable with iterative DP, maybe try recursive DP first, if you are more comfortable with that. Then, as you get better you can switch to iterative DP... just a suggestion.
You are wrong with that iterative thing. In my experience you rarely need to do iterative dp.
Btw I learned a lot from this video when I was learning dp.
I started out with iterative dp. It was some 2D DP task but after seeing recursive dp i think it's more easier than the iterative one. But I've seen a lot of people preferring iterative version. Is there any benefits to it or am i wrong with the difficulty comparison?
Recursive a little bit slower but rarely it will matter.
cries in python
The video is unavailable, can you name the channel, please?
That content is no longer free.
"When you are good at something, never do it for free."
That channel owner was bought by some startup for providing dsa course as far as I know. That video was editorial for this problem.
can you name the channel or channel owner? just for curiosity!
Channel name was CodeNCode
I recommend CSES DP problemset, and this gym made by galen_colin.
The gym has also a video explaining solutions.
You are not allowed to view the contest
I think the gym link u provided is private, i get this when i try to enter it
On low skill levels, I recommend to think in terms of forward DP. It is much easier, having a current state, to see what states could be the next. Just like in BFS (DP is BFS).
In some problems forward DP doesn't work, but it's rare.
Sometimes push-dp (what you said) is nicer, other times pull-dp is nicer, although usually both work.
I usually just implement whichever seems easier to me, so I think it's best to just practice both.
Start with recursive dp. Do a lot of problems with it. Then move to iterative dp, because it's nicer to code, and is usually faster.
You are not alone bro, the first time I came to a DP problem and went to tutorial or solutions, I see the majority of solutions implemented DP in iterative method. But for a novice like me I feel it's so uncomfortable and unnatural, though i still understand the solution. From that point, i started solving more and more DP problems and got used to it in recursive way for a while. Later on, after solving and reading other solutions i feel both ways have their own advantages and feel comfortable with either ways. So if you're just like me, keep solving DP in the way you feel comfortable and maybe you will discover the other way through your journey. Don't panic.
Personally i think "what is the information would i need to contruct a bigger solution" and go from there.
Lets say i want to make a value x using k numbers from a set of n numbers. If i had all the possible values using numbers from 1 to n-1 using at most k-1, i could just try to add the last number to all of those and get the full answer, therefore a dp[x][n][k].
A lot of times it won't be as straightforward but it really is just practice (as much as i hate to say it). I had similar problems not too long ago and by solving problems and learning the ideas i couldnt get i became a lot more confortable with it
I just had a question regarding dp
Can we use memoisation dp and iterative dp as per our comfort or memoisation may result in Memory limit exceeded
I have done dp with memo in many questions(it works fine perfectly) but i am told by my friends to not use memo dp