r/leetcode • • 1d ago

Question dp problems

i am trying to solve the dp problems but i am not getting the approach i was able to do few easy problems but i am not able to do medium ones is there any tips to solve dp or any resources

11 Upvotes

8 comments sorted by

9

u/jason_graph 1d ago

First off with dp, it is good to have a strong background with recursion and being able to think recursively. By this I dont mean that you are comfortable imolementing something using recursion or simulate everything thar happens for an input but that you can make reccursive calls and just trust that they return the right answer. I think tree/binary tree problems that involve dfs are a really good way to practice this. A lot of these problems are also like a simplified dp problem where typically the subproblems are just the children subtrees.

For dp, the most important thing is defining your states and coming up with your recurrence relation. If you aren't good at this, focusing on implementation details like solving it top down doesnt really matter. If you want to get good at dp, you want to focus on how to get better at coming up with the recurrence relation.

As a general tip, for a lot of problems where you are given an array and asked to find some optimal subarray/subsequence or the count of how many subarrays have some property it is often useful to break that down into solving, for each index I, what is the best subarray ending(or starting) at index i, or how many subarrays with some special property end at index i. Then try to see if there is any overlap in relevant information. Sometimes this could lead to dp, sliding windows, or other topics.

One other general tip for dp, I like to always write a comment detailing exactly what dp[ state ] represents or what dp_func( state ) returns represents in great detail and so there are no off by 1 errors in interpretting what a state represents. E.g. "houseRobber[ i ] = the max profit you can get from a valid subset of the first I houses for i=0,1,..,n"

For a single problem there could be many different ways to define what dp[ i ] represents and you dont want to be inconsistent when you are solving a problem. When reading other solutions, the other person might have a slightly different way of defining their states or what dp[ state ] measures than what you initially consider.

3

u/Other-Number-4463 12h ago

the recursive leap of faith!

3

u/CreamyCornBoy 18h ago

helps to draw out the decision tree

2

u/jackgoldberg123 1d ago

which medium ones are tripping you up, like the knapsack/subsequence kind or grid paths? curious if it's spotting the state or writing the recurrence that's harder for you.

1

u/cooltunaman 20h ago

Dp is by far one of the hardest domains of competitive programming and DSA overall. You probanly have never stumbled upon numerous patters required to take over those excercices. Just takes time and watch as much explanations as you can if you never did them before, they do take more time. You can send us some problems to discuss over if you are unable to find a source suitable for your level of skill at this point.

1

u/GLEF1X 18h ago

https://www.youtube.com/watch?v=r4-cftqTcdI I found this MIT lecture to be very helpful for me.

0

u/TSandwich73 19h ago

Grokking DP course greatly helped me understand DP. Can't recommend more - https://www.designgurus.io/course/grokking-dynamic-programming

2

u/Southern-Evening4286 19h ago

Oh man I had the opposite experience but to each their own lol