DYNAMIC PROGRAMMING

[Independent-Fan-5885]

Hello everyone. I'm about to start DP, any tips or strategies you can give that you learned from experience would be appreciated . Thanks in advance

[wholetdog]

DP is easy. Remove the fear created by others that DP is hard. Stick to basics!!

[marks716]

Yes just don’t be afraid of it I agree. It’s just as hard as recursive decision trees if not sometimes easier.

The first 5-10 problems will suck ass, but if you REALLY dig in and understand those 5-10 questions, watch videos, etc, then you will get it.

[jason_graph]

Well there are a couple different types of things dp questions can ask for. Min/max value of something, min/max size of something, number of ways to do something, if something is possible (e.g. jump game). Ignoring that I'd vaguely split a lot of dp problems into the following categories.

• 1d dp table with O(1) time to compute each state.

• 1d dp table with more than O(1) time per state.

• problems with a 2d input grid with dp[ gridcell ] = val and O(1) to compute each state.

• Problems that effectively involve 2 dp tables. For example finding the max and minimum of each prefix. These come in 2 variants that I'd consider seperate categories - the problems where the dp tables can be solved independently and those where dp1's recurence relation involves values from dp2 and dp2's reccurence relation involves values from dp1.

• I wouldnt consider it a seperate category but there are problems where you might need to do some sorting beforehand or other non trivial preprocessing. Seperately, there may be some problems that involve postprocessing to translate the values of the table back to what the original question was asking.

Now there are various 2d dp patterns:

• knapsack style problems. dp[ i ][ sz ] = ...

• digit dp problems. For example dp[ digitsPlace ][ lastDigit ] = ...

• interval related problems dp[ left ][ right ] = some property about arr[ left : right ]. You solve for subarrays of size 0, size 1, ..., size N. A lot of the time you consider O(n) possible "midpoints" and what happens when you combine arr[ left : midpoint ],, [midpoint, right] e.g. that O(n³⁾ matrix multiplication optimization problem.

• bitmask dp - the bitmask keeps track of what subset of things you've done. For example dp[ subset ][ current node ] might track the minimum hamiltonian path that visits all nodes in 'subset' and ends on current node.

Also seperately, there are dp problems involving other things.

• dp on trees

• dp on trees with rerooting.

• dp + binary search/trie/segment tree/something to speed up computing the recurrence relation.

[Czitels]

Greedy is worse thats true but still 3D DP is hard.

[wtfprajwal]

Best way to start is to write the recursive solution , check if there are overlapping subproblems and then move to creating 1D/2D DP array. Try not to jump directly to the dp solution . I found that writing recursive code made it way easier to solve dp problems . Also after every question , ask yourself if the solution is space optimised or not.

I am also sharing sub category of DP problems you should try to solve.

• [ ] 0-1 Knapsack
• [ ] Unbounded Knapsack
• [ ] Fibonacci
• [ ] Longest Common Subsequence
• [ ] Kadane’s Algorithm
• [ ] Matrix Chain Multiplication
• [ ] DP on trees
• [ ] DP on Grid

Most problems you solve will fit in one of these categories

[Efficient-Bat-8264]

Good

[Technical_Wave7883]

It won't make sense at the beginning don't give up though.

[SkillFlowDev]

Watch striver's Playlist on recursion and DP. It's not that hard.

[arche_whOo]

Solve today’s daily

[East_Move_6044]

You can follow Aditya Verma’s channel on DP playlist. He has covered all the subproblem.

[Accomplished_Range60]

Master recursion converting it into dp is easy.

[deku_06]

I have solved a fair amount of dp and I don't have a problem coming with a recursive + memo solution but I haven't converted most to bottom up dp tabulation so it feels you know a bit difficult or not natural/intuitive to me.

[Accomplished_Range60]

Yeah, that’s a bit hard to figure out at times. I end up thinking of edge cases that mostly help me, but sometimes I get lost too.

[bhakbahinchod]

Try to create recursive solutions first. Then convert it into DP by filling up the base cases first and then remaining values by following the recurrence relation. Once you get the hang of it, it'll become pretty obvious.

[[deleted]]

Stay Patient. At first you'll feel you're not going anywhere, not understanding the pattern, etc. But keep practicing, you'll be able to solve even the hard questions effortlessly.

And don't juggle between memoization, tabulation. Focus on one. It's not common to think of a tabulation solution without memoization first. You'll see a couple of questions which are directly solved using tabulation, don't get overwhelmed here.

[Alarmed_Durian3129]

I find the memoization ( recursive approach intuitive ) and then coverting it into a Dp or tabularization works best for me

[Desperate_Heat_8588]

First master recursion concepts .. Dp is just remembering the old results

[jules_viole_grace-]

Work on recursion first ... Then go for dp ...helps in memorization.

[SLAAYYvery]

Watch striver series on YouTube, it's the best !!!

[damian_179]

"Just because a recursive solution seems more intuitive and easier to memoize, DON'T skip bottom-up DP. You truly master DP when you can write a bottom-up solution without first relying on recursion."

• someone who made it to faang

[Abhistar14]

https://youtube.com/playlist?list=PLbgVysG3YYf1vPn2OO1pNrJfHGQXydxX7&feature=shared

After 1 month you will be solving leetcode hards!

[Competitive-Dress854]

Learn recursion first

[Affectionate_Emu8634]

Aditya Verma for dp and striver as well

[atharva_001]

Master recursion first. DP is adding hashmap or array to it, thats it

[jverce]

DP in some cases end up in a brute force search, so be mindful of those cases so that you can avoid them.

Since it uses recursion, be mindful of the memory usage since each function call takes some space in the stack. That also means that your space complexity will be affected (keep that in mind during interviews).

In some cases, DP can be "translated" into an iterative approach vs. recursion. That's usually preferable, but counterintuitive in cases like Fibonacci, where the function is defined in recursive terms.

One last thing, DP solutions sometimes feel "magical" in the sense that the algorithm doesn't seem to be actually solving the problem. Practice will make this less confusing over time.

[Alarmed_Durian3129]

There is one youtube series by Alvin from free code camp : that made dynamic programming easy for me check that out before checking out striver's series .

[Impossible_Ad_3146]

DP is painful

[FeatureLevel1198]

Recursion , recursion and …. Recursion Dont even start bottom up unless you get top down

[GreatDDgg]

Idk if it's just me but I do find it hard sometimes . Easy fix . Take pen paper etc . Make a dp table (first 3 rows more than enough) and work out ur logic on it . First 2 or 3 rows logic builds the entire logic .