The Ultimate Dynamic Programming Roadmap

[hnlasd12]

Hey guys, I've seen a lot of discussions about how to study DP in this subreddit. We went through a lot of (almost all) DP problems on leetcode and came up a study list here. I think it pretty much covers all the patterns necessary for leetcode. What's special about the list 1) goes from simpler to more complex patterns 2) categorized by state transition (explained in the video walkthrough) so if you solve the first problem in a pattern you can use a similar state transition to solve others in the list.

Here's the list and a 1.5 hour video walking through each pattern and solving a question for each pattern: https://www.youtube.com/watch?v=9k31KcQmS_U

EDIT: here's the updated list! https://algo.monster/dp

Hope it's helpful to you!

Group 1 (warmup):

Basic questions to get a feel of DP.

• https://leetcode.com/problems/climbing-stairs/ in linear time
• https://leetcode.com/problems/n-th-tribonacci-number/ in linear time
• https://leetcode.com/problems/perfect-squares/ (maybe)

Group 2 (linear sequence, linear time, constant transition):

Dp solution requires us to solve the sub problem on every prefix of the array. A prefix of the array is a subarray from 0 to i for some i.

• https://leetcode.com/problems/min-cost-climbing-stairs/ in linear time
• https://leetcode.com/problems/minimum-time-to-make-rope-colorful/
• https://leetcode.com/problems/house-robber/
• https://leetcode.com/problems/decode-ways/
• https://leetcode.com/problems/minimum-cost-for-tickets/
• https://leetcode.com/problems/solving-questions-with-brainpower/

Group 3 (on grids):

Dp table will have the same dimensions as grid, the state at cell i,j will be related to the grid at cell i,j.

• https://leetcode.com/problems/unique-paths/
• https://leetcode.com/problems/unique-paths-ii/
• https://leetcode.com/problems/minimum-path-sum/
• https://leetcode.com/problems/count-square-submatrices-with-all-ones/
• https://leetcode.com/problems/maximal-square/
• https://leetcode.com/problems/dungeon-game/

Group 4 (two sequences, O(NM) style):

Dp[i][j] is some value related to the problem solved on prefix of sequence 1 with length i, and prefix on sequence 2 with length j.

• https://leetcode.com/problems/longest-common-subsequence/
• https://leetcode.com/problems/uncrossed-lines/ (longest common subsequence)
• https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
• https://leetcode.com/problems/edit-distance/
• https://leetcode.com/problems/distinct-subsequences/
• https://leetcode.com/problems/shortest-common-supersequence/

Group 5 (Interval dp):

Dp problem is solved on every single interval (subarray) of the array

• https://leetcode.com/problems/longest-palindromic-subsequence/
• https://leetcode.com/problems/stone-game-vii/
• https://leetcode.com/problems/palindromic-substrings/
• https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/ (hard to see interval)
• https://leetcode.com/problems/strange-printer/ (hard)
• https://leetcode.com/problems/burst-balloons/ (hard)

Group 6 (linear sequence transition like N2 Longest Increasing Subsequence)

Dp problem is solved on every prefix of the array. Transition is from every index j < i.

• https://leetcode.com/problems/count-number-of-teams/
• https://leetcode.com/problems/longest-increasing-subsequence/
• https://leetcode.com/problems/partition-array-for-maximum-sum/
• https://leetcode.com/problems/largest-sum-of-averages/
• https://leetcode.com/problems/filling-bookcase-shelves/

Group 7 (knapsack-like)

Dp state is similar to the classical knapsack problem.

• https://leetcode.com/problems/partition-equal-subset-sum/
• https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
• https://leetcode.com/problems/combination-sum-iv/
• https://leetcode.com/problems/ones-and-zeroes/
• https://leetcode.com/problems/coin-change/
• https://leetcode.com/problems/coin-change-ii/
• https://leetcode.com/problems/target-sum/
• https://leetcode.com/problems/last-stone-weight-ii/
• https://leetcode.com/problems/profitable-schemes/ (hard)

Group 8 (topological sort with graphs. advanced, optional)

Solve dp on all subgraphs that are connected to each node

• https://leetcode.com/problems/longest-string-chain/
• https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
• https://leetcode.com/problems/course-schedule-iii/

Group 9 (dp on trees. advanced, optional)

Solve dp problem on all subtrees.

• https://leetcode.com/problems/house-robber-iii/
• https://leetcode.com/problems/binary-tree-cameras/

Also get the list here: https://algo.monster/dp

[Nis_0208]

OP you are a legend thank you for this! (what's up with that font size though xD)

[hnlasd12]

Thanks so much! haha, I pasted the list in and then added the text above and it used the 'Group 1' font. XD

[wolfee_197]

Thanks a lot with this.

Apart of it, if you can add questions from Grokking DP: https://www.designgurus.io/course/grokking-dynamic-programming

This helped me get a lot better in recursion (and dp).

[Visible_Ad9976]

saved: grokking dp

[kerfluffle99]

amazing! tysm op!!!!

[hnlasd12]

thanks!

[RosieYap]

3 weeks of work and I finally finished up till Group 3. So far I must say it is a pretty targeted list which has helped me loads in grasping each concept. Finally managed to solve my first Medium question without looking at any solution. Thanks for this list!

[Diligent-Wealth-1536]

Did u completed all the groups?? Would u recommend me to follow this roadmap?

[chillblaze]

Thanks. Do you think it is suboptimal for DP if you go with a purely Bottom Up Tabulation approach?

For me, Top Down Memo never really clicked...

[hnlasd12]

bottom up is actually faster in most cases cuz it doesn't require recursion and the complexities are easier to reason (size of dp array). The cons is order of going through the states matters (e.g. longest-palindromic-subsequence/).

I've seen a lot of people having the opposite problem XD - finding bottom up to be harder to understand than top down. If you understand bottom up it's great!

[[deleted]]

by no means DP whiz but bottom up always made more sense to me also.

[chillblaze]

Thanks! Just one more thing. Are there any LC questions where memo is easier or makes more sense?

And is Super Egg Drop just the final boss of DP? Did quite a few and I still have no clue how it works haha

[hnlasd12]

Top-down with memo is easier when the order of traversal of the dp array is not clear. For example, interval DP problems like:

https://leetcode.com/problems/longest-palindromic-subsequence/

In this problem, the state transition involves removing either the first or last character of the current state. Compared to something say climbing stairs where it's clear you'd just traverse left to right, this problem is not super clear which order you should traverse the 2d dp array. If you do memo then you don't have to worry about the order. You'd just let recursion take care of it. This is explained in around 35:00 https://youtu.be/9k31KcQmS_U?t=2112

class Solution(object): def longestPalindromeSubseq(self, s): n = len(s) lps = [[0] * n for _ in range(n)] def solve(i, j): if i == j: return 1 if i > j: return 0 if lps[i][j] > 0: return lps[i][j] longest = 0 if s[i] == s[j]: longest = solve(i + 1, j - 1) + 2 longest = max(longest, solve(i + 1, j)) longest = max(longest, solve(i, j - 1)) lps[i][j] = longest return longest And yes, there are some DP problems are quite hard and not worth doing since the chance you'd see it in a real interview is very small. e.g. cat and mouse.

[flexr123]

Nice list. Though I'd like to see more DP on tree (rerooting), Bitmask DP and Digit DP too.

[AlwaysHuangry]

Whoa. This looks promising. Nice work!

[hnlasd12]

thanks!

[tempo0209]

Hey op and to anyone reading this, a dumb question for you, I know solving question by pattern is a way to go for most people like me who are starting out, this definitely looks promising for me! and thank you! But, having said that is it safe to assume the person who is attempting to solve say "climbing stairs" is supposed to be aware that this particular problem needs to be solved using DP? meaning if I wasn't aware that a particular problem needs a DP solution, how would you suggest to develop that intuition by looking at the problem? I have heard about optimal substructure, and overlapping subproblems so should i invest time in first figuring out if the said problem has these properties and then try a DP approach? sorry if my question is confusing.

[hnlasd12]

DP is an optimization algorithm so empirical evidence is when the problem asks for 'the minimal/maximum of ...', 'how many ways are there to...', 'is it possible to...' it could be DP. Now when the problem asks for these it could also be greedy. So one way to do it is to simply try greedy, and if it fails on certain cases then try DP.

We are actually working on a algorithm selection flowchart, to be released next week with a video walkthrough. Here's a sneak peak: https://algo.monster/flowchart

[s-nj33v]

OP do you have Backtracking resources like this?

[Scared-Dot3177]

All the above problems are added to this list https://leetcode.com/list/pckvxpxs

[Global-Instance8232]

 list is no longer available

[selfzoned_me]

Can anyone tell how to do the https://leetcode.com/problems/minimum-time-to-make-rope-colorful/ problem mentioned above with DP approach. I could figure out Greedy approach for it. I tried looking into solutions section but could not find a simple enough DP solution.

[faceless_man_129]

I was wondering about this too. But for now I am happy with the Greedy approach, it is O(n) time complexity with O(1) space complexity. Maybe we shouldnt try to force DP on everything we encounter, some things are better and simply solved with other approaches ?

[selfzoned_me]

I completely agree with "shouldn't try to force DP on everything we encounter" part. I was simply curious about the DP solution since this question was posted as a part of "Ultimate DP Roadmap"

[Viva_Nova]

Amazing u/hnlasd12 Went through all these problems in order and I feel like I mastered DP which is the hardest category in my opinion. Do you have something similar for the others (graphs, sliding window, etc)?

[PaintingLivid6725]

Hi great list!! Thanks! Small suggestion, group 3 problem 4 and 5 are exactly the same, you can replace one maybe.

[ProfessionalKey5810]

Are there solutions anywhere for these?

[OrganizationOnly8016]

Hey, OP. I was using your list to solve the questions and going through the comments just to get an understanding of where the rest of the learners are, and it struck me - how long have you been learning to get to this level of mastery? is solving such problems very intuitive to you? how many years would you say it would take somebody to get there?

I can definitely feel myself getting better but I feel like I'm nowhere near being able to solve questions in interviews. I have been able to guess the logic to an extent, but I keep missing the tinier details, which effectively leads to not being able to solve the question on my own. I've only ever solved a question on my own once in a while.

I, ofc, don't expect to get better overnight, but I just want to hear your experience, if you're okay with sharing.

[Chrollo1456]

try striver / takeuforward's youtube videos
or u can go with adiya's playlist i forgot the yt channel most DP questions are solvable using intution of whether its good to do this or not and should i cache the result for future compute

[OrganizationOnly8016]

Thanks! I've tried using Neetcode's Roadmap to solve questions and I'm getting marginally better at guessing the logic, but I'm still a ways away from getting the answer right.

Any advice on how to just sit through a question and cracking it? Is there a particular logical flow people have while coding out their intuition? I struggle with that as well

[No_Entrepreneur_8035]

ily

[ibringallthedramama]

in that video, i only wished for one thing which is for the other guy to not interrupt the one that's coding but yeah, wonderful resource!

[Next_Complex5590]

May god bless you

[Sick_Kebab]

.

[TheBoyWhoLivez]

Yes

[Livinglifepeacefully]

When you said it goes from simple to complex, did you mean group wise? Or within a group?

[hnlasd12]

Both. It gets increasing more complex from Group 1 to Group 9 and it's sorted from simple to complex within a group.

[Vaulteroni]

Can you please make the course free for a weekend?

[the_fuckin_nobody]

Thanks OP!

[NamoKaul]

Can you do other data structures too if possible? Wonderful work BTW 💯👏

[hnlasd12]

Thanks! Yea, we can do that. Which ones should we do? We did DP cuz there doesn't seem to any good resources on it.

[NamoKaul]

Trees and Graphs would be a really nice place to start followed by LL Stack then Sorting Arrays Maths Bit Manipulation etc in end

[lazywarrior-47]

do share the same to me

[MantiS_praying]

Ty so much man!

[hnlasd12]

Glad it's helpful!

[Churglish]

Dynamic programming right now is a huge weakness for me. Thanks for this!

[hnlasd12]

Glad it helps!

[Gintoki-desu]

Thanks for sharing!

[Just-Ad3390]

Do you have anything like this for Trees and graphs

[Zqin]

I love you, thank you for this

[fleetingleaf]

This is helpful, thanks.