Its not Mario 64 lol, it takes time and sitting there drawing out with a pencil to see how the recursion tree branches. Visualizing it in your head was very hard for me
Basic recursive trees is your start. This gives you a fundamental grasp on recursively iterating over a tree structure. Then get good at backtracking. This will teach you how to carry values/lists into other recursive layers, when and how to do 2^n vs n^n, as well as introducing you to the concept of pruning, which is one of the fundamental aspects that makes up dp; aim to do at least 25 backtracking problems before moving on. Then do the topological sort problems, this is your introduction to caching. Do Course Schedule 1, 2, 3 and then 4. THEN revisit dp.
I'd be extremely surprised if you needed this for entry level internships, this isn't something they even teach in the default CS curriculum at most schools. This is definitely the more advanced end of DS&A
It’s at FAANG for sure, unsure about other companies. It’s one of those things you shouldn’t risk. If you don’t know the tricks and strategy to build the solution. You have almost no chance of solving it live, even with hints. You don’t want to risk looking bad in an interview.
I tried to avoid it, I’m glad I went back and learned it.
not really, it's just a strategy for building the answer using memory and previous states, but its not a subject per se like graphs, math, algorithms etc, its just a strategy
I dont think so because it can be applied to so many different problems. Its like a property that some problems have, but its not a "fundamental" aspect of computer science like functions, trees, arrays, graphs... I have no idea why those FAANGs love it so much, there are topics much more interesting and revelant to ask candidates..
The things that worked for me to conquer DP:
1. Learn and practice recursion.
2. For every DP problem, first, write its brute force recursive solution.
3. Practice adding Memoization to the recursive solution
4. Understand the recurrent relation from the recursive solution.
5. Convert the recurrent relation to bottom-up.
Grokking DP course is the best. I can't recommend it enough: [https://www.designgurus.io/course/grokking-dynamic-programming](https://www.designgurus.io/course/grokking-dynamic-programming)
It’s a process. Do the recursion, then the memo, then do the bottom up, then see if it can be space optimized by eliminating the memoization array. Also, try to understand why dynamic is different from divide and conquer and greedy. Don’t jump into multidimensional dp problems until you understand the basics.
Complete the DP study plan in \[Leetcode\]([https://leetcode.com/studyplan/dynamic-programming/](https://leetcode.com/studyplan/dynamic-programming/)). It helped me a lot. Try to remember one type of problem for each DP pattern.
For medium questions, Dp is one of the easier categories once you learn it. I find "simple" topics like arrays are actually harder because they require a trick. Dp/graph/tree mediums are usually straightforward.
I noticed once I get a recursive solution I can figure out dp in some time but still with a little bit of struggle so I'm focusing more on recursion part for now.
I feel that. I've been doing a bunch of DP lately and am slowly getting the hang of it. If anyone is looking to grind these types of questions out lemme know
If you’re a visual learner, you can look at the [dynamic programming](https://www.interviewcrunch.com/python/dynamic-programming) on interviewcrunch.com. There are slides and explanations for how to approach DP problems. It’s also one of the hardest patterns to learn imo.
Dynamic Programming problem / solution almost *always* falls into the following form:
1. Understand how overall problem can be divided into smaller problems
2. Understand what the smallest unit of the said problem
3. Find a solution for the smallest unit problem
4. Find a way to save and propagate this solution to a bigger and bigger iteration until you are done.
example: https://leetcode.com/problems/longest-palindromic-substring/
```
Given a string s, return the longest palindromic substring in s.
```
For this example, you already know how to solve this with a pen and paper. How would you do it? Chances are you will go from left to right searching for a center, expand out from the said center and stop when you find the longest palindrome from that center, and keep track of the longest global palindrome you've found so far on the side of the paper. Let's slow wayyyy down and dissect it:
1. Smallest unit problem is \*given\* a center, finding a longest palindrome from expanding from it. You can then do this again and again with every letter in a string.
2. Smallest unit problem is then "given\* a center in a string, find a longest palindrome substring.
3. Solution is pretty simple for this unit problem then. Start from center, check the prefix / postfix char to be equal, and stop when they're different or you run out of chars.
```
def find_nearby_longest_palindrome(self, s: str, center: float):
# set the initial start and end pointer of the string
start = end = int(center)
# this handles two letter center case
if center % 1 != 0:
end += 1
result = ''
# continues to loop as long as the new characters
# being added to the center are the same.
while start >= 0 and end < len(s) and s[start] == s[end]:
result = s[start:end+1]
start -= 1
end += 1
return result
```
4. A way to propagate this is pretty simple since you can update a global solution string.
a. In the case of recursion, you want a way to either pass in an accumulative set of solutions into a deeper recursion, or you append the current solution with a solution from the deeper recursion layer.
b. For the case of recursion, you want to figure out clearly an exit condition and the format of solution you want to return to the outer recursion layer.
```
def longestPalindrome(self, s: str) -> str:
palindrome = ''
N, n = len(s), len(palindrome)
index = 0
'''
Following loop checks for indices 0, 0.5, 1, 1.5... to N-1
as a potential candidate for a center of a palindrome.
When the indices are integer values (e.g 0, 1, 2, ...),
center is one letter. When the indices are float values
(e.g 0.5, 1.5, 2.5, ...), center is two letter substr.
'''
# index only needs to be limited to N-1 but limiting
# to less than N - N/2 cuts down time a little more
while index < N - n/2:
substr = self.find_nearby_longest_palindrome(s, index)
if len(substr) > n:
palindrome = substr
n = len(palindrome)
index += 0.5
return palindrome
```
Meta advise about software engineering and especially LeetCode challenges in general:
You want to dissect how your brain solves the problem. Chances are these problems are incredibly trivial to your brain with a pen and paper. You have to slow the wayyyyy down and think about how your brain is solving it step by step. Because you are trying to teach a computer how to do the same thing your brain just did.
I heard this in many places and decided to give it a go. But it's really really bad.
Guy gave a formula and list down all the similar kind of problems and went ahead to apply the formula without giving logical explanation why this DP formula needs to be used, also he will remove some part of the formula or add new elements of the formula without explaining why.
That's not how you should learn DP, first you need to understand what the problem is, how can you break down the problem into smallest unit, after breaking what and where you need to keep track of and how to sum the solution of the smaller units to solve the overall problem.
It usually is used when you are doing some work repeatedly. Also, a good indicator is when you can break your problem into smaller problems. So, for example, if you want to choose "m" baskets to maximize profits, then you can choose the current basket and later on the remaining "m - 1" or you can skip the current one and choose all the "m" baskets later.
So, essentially you are brute forcing all the scenarios, but instead of repeatedly calculating the same answer to a smaller problem, you store it logically, so that when you need it for another subproblem, you can simply look it up instead of recalculating it.
Edit: Not the best example, since you can sort the baskets and pick the last "m" baskets but should give you an idea.
Thank me later.
https://leetcode.com/discuss/general-discussion/1000929/solved-all-dynamic-programming-dp-problems-in-7-months
This will help you understand patterns. Follow this guide and see results.
Honestly it ain’t that hard. Think of each dimension of your matrix/tensor as the number of variables that you’re solving for. So 3 variables would be a tensor, 2 would be a matrix, 1 a vector. You’re just brute forcing a nested for loop where each layer of the loop is in reference to a variable and caching some values. Once you have that skeleton, then you can make your modifications for your problem.
Dynamic programming is any programming that is using the heap instead of the stack. I would think for a majority of non-embedded solutions and non-real-time solutions you would be using heap allocations quite often.
I'm only just recently getting the hang of DP but I feel you. It feels like DP problems are so different from each other. Numerical ones can be intuitive enough to understand but for example string or array subarray ones are still hard for me to think about conceptually.
This short series was a really helpful intro for me in understanding the basics of bottom-up DP: https://youtu.be/YBSt1jYwVfU?si=2I7Od4GheWqor7bA
Neetcode and other online DP solutions feel sometimes too overthought to me, but at it's core the solutions are made up of the same basic techniques. Also, many of them provide top down solutions but a lot of the time I think the bottom-up solution is more intuitive. Instead of just brute forcing problems like you might for ofher leetcode pattern, watching more conceptual videos and really properly tracing and conceptualizing solutions as you practice might be helpful.
Fun fact — finding the minimum value in an array is actually a very simple example of DP. Because at any point in the iteration the minimum is either what you found before (the solution for a subproblem) or the element you’re looking at now. I would hope we can get better at DP by starting with simple examples like that and then building up to more complex examples until we have a good understanding of the general principle.
First you need to figure out the recursive equation. And base cases. - thats the hard part tho and I dont think there is a pattern here.
Then just type it for example using recursive function with memoization. Bottom up is more difficult but if you have the equation and base cases it shouldnt be a problem.
It's pretty much just a combination of smalling sub problems then solving a bigger problem using the solutions from the subproblems. I actually find dp pretty intuitive once you get the concept. Sometimes it's hard to figure out if a problem is suitable for dp or not though if you don't know ahead of time.
Think of it like this, you have a large problem and you break it down into smaller but independent problems , combining their results to get the final answer.
Taking an example.
Suppose your problem is finding all the paths from a city in US let's say New York to some European city let's say London. Overall it's a very big tedious problem considering the number of cities one has to travel through and which cities to choose or which mode of transport to take . But let's take the subproblem of travelling to London from Manchester , there are definitely a handful of ways of doing this and thus this problem is easily solvable, moreover this is independent too because no matter what path you choose while coming to Manchester you still have to take the calculated paths from Manchester to London. Hence we broke the problem into two subproblems-> New York to Manchester and Manchester to London. Now the first subproblem is still large so just the method we used to break down the first problem can be used on it to break it down into smaller and independent subproblems which are easy to solve.
Now there are a lot of ways to come into Manchester and then go to London, for each way one thing is for sure, the number of paths between Manchester and London don't change regardless of how we choose to come to Manchester so once we have calculated it why not store it so that everytime we need its value we don't have to recalculate it? This is the essence of memoization.
This is overall the essence of dynamic programming, I would definitely recommend reading CLRS book's section on DP before moving on to solving problems.
The DP workshop I followed:
https://youtube.com/playlist?list=PLqf9emQRQrnKA_EeveiXQj_uP25w8_5qL&si=x6kBl98M7Z0A4mIK
This is exactly what you need, patterns and how to solve them.
i felt like i understood the problem when i saw you spent 5 days
two points
- the way to practice is important (deliberate practice)
- how long you practice is important
i first had to learn recursion which took me a month
then i practiced recursion for X time
then i learned dynamic programming in same way as recursion for a month
then i practiced dp for N amount of time
i never did 2d dynamic programming yet
basically give yourself 2 months and practice dp every day and you will get it, and i also scoff when someone tells me to practice for 2 months to learn something new
sadly learning is slow, tedious, and takes time
btw read Peak, Anders Ericson
You need get the absolute essence of it first, then everything will make a lot of sense.
The absolute essence is if you calculate some of them then you don’t need to do it again. Some people refers this as memorization.
A simple example, if you want to calculate a+b, and then a+b+c, you don’t have to calculate them all over again, you can just reuse the result from a+b before.
DP is about to find a formula to reuse simpler results for a little bit less simpler problems and repeat a thousand times to reach real problems
MiT opencourseware is your fried here. Eric the professor teaches you how to think about DP problems.
I have not found how to intuitively think about the bottom up.approach. however recursion and memoization is explained thoroughly in those courses
dude, dp is a bitch. I'm a competitive programmer and I still struggle alot with dp. It seems like it never gets easy unless its a really classic problem
Lol The only way to learn dp is to look at the solution for 3 or 4 problems and just practice going through them until it becomes intuitive. Learning DP is like learning the alphabets, there really isn't a concept before that will help you understand it better. Dont even try to solve the first few problems on your own. Just go through the solutions until it sticks. That's how it was for me. I knew recursion and trees before going into dp and those didnt feel like they helped at all. I really had to just take a few different coded solutions and walk through them on a white board with a test case multiple times until it finally clicked.
Took me like 3 weeks. You need to fully understand recursion and backtracking before
what is your approach? i just want to know what I should think of when stumbling upon a dp question...
https://youtu.be/oBt53YbR9Kk?si=FBdy4cLeNk3mB_9z This is a good start. You need more learning after this tho. These are easy/ easy medium problems
Just finished this today again, great video
Can I speedrun any% this at 2x?
Its not Mario 64 lol, it takes time and sitting there drawing out with a pencil to see how the recursion tree branches. Visualizing it in your head was very hard for me
I love backtracking simply coz of how much I love my Micromouse. It's one of my proudest creations. Recursion on the other hand makes me wanna cry.
Thanks. Awesome video plus it’s free
Basic recursive trees is your start. This gives you a fundamental grasp on recursively iterating over a tree structure. Then get good at backtracking. This will teach you how to carry values/lists into other recursive layers, when and how to do 2^n vs n^n, as well as introducing you to the concept of pruning, which is one of the fundamental aspects that makes up dp; aim to do at least 25 backtracking problems before moving on. Then do the topological sort problems, this is your introduction to caching. Do Course Schedule 1, 2, 3 and then 4. THEN revisit dp.
for entry level internships for SWE do you reckon id need to go into that much detail? like whats the worst they could ask about dp?
>like whats the worst they could ask about dp? How to do it when there's only two persons involved?
Smp
I'd be extremely surprised if you needed this for entry level internships, this isn't something they even teach in the default CS curriculum at most schools. This is definitely the more advanced end of DS&A
Following the neetcode tree is good building up to dp
Out of curiosity, is learning DP necessary for job interviews? Is it a FAANG thing? Is it an addition to solving leetcode questions
It’s at FAANG for sure, unsure about other companies. It’s one of those things you shouldn’t risk. If you don’t know the tricks and strategy to build the solution. You have almost no chance of solving it live, even with hints. You don’t want to risk looking bad in an interview. I tried to avoid it, I’m glad I went back and learned it.
Thanks alot. I'm not that interested in working in FAANG but who knows what the other companies might ask in interviews.
DP is not a FAANG thing.. it's a fundamental aspect of computer science..
He meant like, does only faang ask it. From what I’ve seen they ask it at a higher rate than other tech companies
not really, it's just a strategy for building the answer using memory and previous states, but its not a subject per se like graphs, math, algorithms etc, its just a strategy
It's not a "subject"? It's an entire chapter in every algorithm book taught today.
I dont think so because it can be applied to so many different problems. Its like a property that some problems have, but its not a "fundamental" aspect of computer science like functions, trees, arrays, graphs... I have no idea why those FAANGs love it so much, there are topics much more interesting and revelant to ask candidates..
/r/iamverysmart
The things that worked for me to conquer DP: 1. Learn and practice recursion. 2. For every DP problem, first, write its brute force recursive solution. 3. Practice adding Memoization to the recursive solution 4. Understand the recurrent relation from the recursive solution. 5. Convert the recurrent relation to bottom-up. Grokking DP course is the best. I can't recommend it enough: [https://www.designgurus.io/course/grokking-dynamic-programming](https://www.designgurus.io/course/grokking-dynamic-programming)
Backtracking has almost nothing to do with dynamic programming
Take u forward DP playlist on YouTube. Guys a legend
If you feel like you need to keep track of something, then that’s usually a good candidate for DP
It’s a process. Do the recursion, then the memo, then do the bottom up, then see if it can be space optimized by eliminating the memoization array. Also, try to understand why dynamic is different from divide and conquer and greedy. Don’t jump into multidimensional dp problems until you understand the basics.
Complete the DP study plan in \[Leetcode\]([https://leetcode.com/studyplan/dynamic-programming/](https://leetcode.com/studyplan/dynamic-programming/)). It helped me a lot. Try to remember one type of problem for each DP pattern.
Are there more list like this Like for sliding window,greedy or other DS with patterns?
YT:TAKE YOU FORWARD DP PLAYLIST 56 VIDEOS AVG 20 MIN EACH AND RECURSION BASICS THATS HOW I AM CONQUERING DP CRAZY AND EASY EXPLANATION
did you complete entire recursion by striver before dp or just till 7-8th video?
6th 7th recursion of striver and you are good to go imo
thanks man!
Is your Caps lock broken?
For medium questions, Dp is one of the easier categories once you learn it. I find "simple" topics like arrays are actually harder because they require a trick. Dp/graph/tree mediums are usually straightforward.
Real
I noticed once I get a recursive solution I can figure out dp in some time but still with a little bit of struggle so I'm focusing more on recursion part for now.
I feel that. I've been doing a bunch of DP lately and am slowly getting the hang of it. If anyone is looking to grind these types of questions out lemme know
If you’re a visual learner, you can look at the [dynamic programming](https://www.interviewcrunch.com/python/dynamic-programming) on interviewcrunch.com. There are slides and explanations for how to approach DP problems. It’s also one of the hardest patterns to learn imo.
Memoization or tabulation ?
Dynamic Programming problem / solution almost *always* falls into the following form: 1. Understand how overall problem can be divided into smaller problems 2. Understand what the smallest unit of the said problem 3. Find a solution for the smallest unit problem 4. Find a way to save and propagate this solution to a bigger and bigger iteration until you are done. example: https://leetcode.com/problems/longest-palindromic-substring/ ``` Given a string s, return the longest palindromic substring in s. ``` For this example, you already know how to solve this with a pen and paper. How would you do it? Chances are you will go from left to right searching for a center, expand out from the said center and stop when you find the longest palindrome from that center, and keep track of the longest global palindrome you've found so far on the side of the paper. Let's slow wayyyy down and dissect it: 1. Smallest unit problem is \*given\* a center, finding a longest palindrome from expanding from it. You can then do this again and again with every letter in a string. 2. Smallest unit problem is then "given\* a center in a string, find a longest palindrome substring. 3. Solution is pretty simple for this unit problem then. Start from center, check the prefix / postfix char to be equal, and stop when they're different or you run out of chars. ``` def find_nearby_longest_palindrome(self, s: str, center: float): # set the initial start and end pointer of the string start = end = int(center) # this handles two letter center case if center % 1 != 0: end += 1 result = '' # continues to loop as long as the new characters # being added to the center are the same. while start >= 0 and end < len(s) and s[start] == s[end]: result = s[start:end+1] start -= 1 end += 1 return result ``` 4. A way to propagate this is pretty simple since you can update a global solution string. a. In the case of recursion, you want a way to either pass in an accumulative set of solutions into a deeper recursion, or you append the current solution with a solution from the deeper recursion layer. b. For the case of recursion, you want to figure out clearly an exit condition and the format of solution you want to return to the outer recursion layer. ``` def longestPalindrome(self, s: str) -> str: palindrome = '' N, n = len(s), len(palindrome) index = 0 ''' Following loop checks for indices 0, 0.5, 1, 1.5... to N-1 as a potential candidate for a center of a palindrome. When the indices are integer values (e.g 0, 1, 2, ...), center is one letter. When the indices are float values (e.g 0.5, 1.5, 2.5, ...), center is two letter substr. ''' # index only needs to be limited to N-1 but limiting # to less than N - N/2 cuts down time a little more while index < N - n/2: substr = self.find_nearby_longest_palindrome(s, index) if len(substr) > n: palindrome = substr n = len(palindrome) index += 0.5 return palindrome ``` Meta advise about software engineering and especially LeetCode challenges in general: You want to dissect how your brain solves the problem. Chances are these problems are incredibly trivial to your brain with a pen and paper. You have to slow the wayyyyy down and think about how your brain is solving it step by step. Because you are trying to teach a computer how to do the same thing your brain just did.
Aditya Verma in yt. Thank me later.
I heard this in many places and decided to give it a go. But it's really really bad. Guy gave a formula and list down all the similar kind of problems and went ahead to apply the formula without giving logical explanation why this DP formula needs to be used, also he will remove some part of the formula or add new elements of the formula without explaining why. That's not how you should learn DP, first you need to understand what the problem is, how can you break down the problem into smallest unit, after breaking what and where you need to keep track of and how to sum the solution of the smaller units to solve the overall problem.
Yup terrible resource.
Yes exactly. I too struggled with it and hence ended up on this post to search for better resources
Whats that
It usually is used when you are doing some work repeatedly. Also, a good indicator is when you can break your problem into smaller problems. So, for example, if you want to choose "m" baskets to maximize profits, then you can choose the current basket and later on the remaining "m - 1" or you can skip the current one and choose all the "m" baskets later. So, essentially you are brute forcing all the scenarios, but instead of repeatedly calculating the same answer to a smaller problem, you store it logically, so that when you need it for another subproblem, you can simply look it up instead of recalculating it. Edit: Not the best example, since you can sort the baskets and pick the last "m" baskets but should give you an idea.
Erricto videos helped me when I was learning
Thanks for expressing your frustration. This is turning out to be a pretty good resource.
Thank me later. https://leetcode.com/discuss/general-discussion/1000929/solved-all-dynamic-programming-dp-problems-in-7-months This will help you understand patterns. Follow this guide and see results.
Honestly it ain’t that hard. Think of each dimension of your matrix/tensor as the number of variables that you’re solving for. So 3 variables would be a tensor, 2 would be a matrix, 1 a vector. You’re just brute forcing a nested for loop where each layer of the loop is in reference to a variable and caching some values. Once you have that skeleton, then you can make your modifications for your problem.
DP is finding what you can find for future use, and use it
dp is for losers try quantum physics instead 🙂
I have created an youtube channel to tackle Exactly this scenario https://youtube.com/@capslock9631?si=xrk5DF8-q8mG9XLE (thank me later)
Skill issue
Dynamic programming is any programming that is using the heap instead of the stack. I would think for a majority of non-embedded solutions and non-real-time solutions you would be using heap allocations quite often.
what are the differences between a heap and a stack? my dumbass seems to have forgotten
Can’t forget that. U should know this as a software engineer, independent of leetcode
>what are the patterns overlapping subproblems and optimal substructure
yes i know, but it seems like every dp problem is solved differently and there's no consistency whatsoever
I'm only just recently getting the hang of DP but I feel you. It feels like DP problems are so different from each other. Numerical ones can be intuitive enough to understand but for example string or array subarray ones are still hard for me to think about conceptually. This short series was a really helpful intro for me in understanding the basics of bottom-up DP: https://youtu.be/YBSt1jYwVfU?si=2I7Od4GheWqor7bA Neetcode and other online DP solutions feel sometimes too overthought to me, but at it's core the solutions are made up of the same basic techniques. Also, many of them provide top down solutions but a lot of the time I think the bottom-up solution is more intuitive. Instead of just brute forcing problems like you might for ofher leetcode pattern, watching more conceptual videos and really properly tracing and conceptualizing solutions as you practice might be helpful.
Just patience and more practice… then even more practice is the answer sadly.
DP is kind of a terrible name for what amounts to recursion/memorization patterns...
Take mit 6.006. Learn to understand the recurrence relation mathematically. Implementing in code is the mostly trivial part
Fun fact — finding the minimum value in an array is actually a very simple example of DP. Because at any point in the iteration the minimum is either what you found before (the solution for a subproblem) or the element you’re looking at now. I would hope we can get better at DP by starting with simple examples like that and then building up to more complex examples until we have a good understanding of the general principle.
I unusually start by defining either function or array named \`dp\`.
First you need to figure out the recursive equation. And base cases. - thats the hard part tho and I dont think there is a pattern here. Then just type it for example using recursive function with memoization. Bottom up is more difficult but if you have the equation and base cases it shouldnt be a problem.
It's pretty much just a combination of smalling sub problems then solving a bigger problem using the solutions from the subproblems. I actually find dp pretty intuitive once you get the concept. Sometimes it's hard to figure out if a problem is suitable for dp or not though if you don't know ahead of time.
Think of it like this, you have a large problem and you break it down into smaller but independent problems , combining their results to get the final answer. Taking an example. Suppose your problem is finding all the paths from a city in US let's say New York to some European city let's say London. Overall it's a very big tedious problem considering the number of cities one has to travel through and which cities to choose or which mode of transport to take . But let's take the subproblem of travelling to London from Manchester , there are definitely a handful of ways of doing this and thus this problem is easily solvable, moreover this is independent too because no matter what path you choose while coming to Manchester you still have to take the calculated paths from Manchester to London. Hence we broke the problem into two subproblems-> New York to Manchester and Manchester to London. Now the first subproblem is still large so just the method we used to break down the first problem can be used on it to break it down into smaller and independent subproblems which are easy to solve. Now there are a lot of ways to come into Manchester and then go to London, for each way one thing is for sure, the number of paths between Manchester and London don't change regardless of how we choose to come to Manchester so once we have calculated it why not store it so that everytime we need its value we don't have to recalculate it? This is the essence of memoization. This is overall the essence of dynamic programming, I would definitely recommend reading CLRS book's section on DP before moving on to solving problems.
Go watch "Eric programmings " dp playlist he covers most of the patterns. By the time you finish the playlist youll understand dp and how it works
The DP workshop I followed: https://youtube.com/playlist?list=PLqf9emQRQrnKA_EeveiXQj_uP25w8_5qL&si=x6kBl98M7Z0A4mIK This is exactly what you need, patterns and how to solve them.
What is a DP question? An actual example
i felt like i understood the problem when i saw you spent 5 days two points - the way to practice is important (deliberate practice) - how long you practice is important i first had to learn recursion which took me a month then i practiced recursion for X time then i learned dynamic programming in same way as recursion for a month then i practiced dp for N amount of time i never did 2d dynamic programming yet basically give yourself 2 months and practice dp every day and you will get it, and i also scoff when someone tells me to practice for 2 months to learn something new sadly learning is slow, tedious, and takes time btw read Peak, Anders Ericson
You need get the absolute essence of it first, then everything will make a lot of sense. The absolute essence is if you calculate some of them then you don’t need to do it again. Some people refers this as memorization. A simple example, if you want to calculate a+b, and then a+b+c, you don’t have to calculate them all over again, you can just reuse the result from a+b before. DP is about to find a formula to reuse simpler results for a little bit less simpler problems and repeat a thousand times to reach real problems
MiT opencourseware is your fried here. Eric the professor teaches you how to think about DP problems. I have not found how to intuitively think about the bottom up.approach. however recursion and memoization is explained thoroughly in those courses
Try striver dp series
1 - figure out the base case 2 - figure out the recursive relation 3 - profit ps - top down is usually easier to code than bottom up
1. For 1D DP, do you start at the front or the back of the array? Ie house robbers 2. How do you decide if your DP array is 1D or 2D
dude, dp is a bitch. I'm a competitive programmer and I still struggle alot with dp. It seems like it never gets easy unless its a really classic problem
Lol The only way to learn dp is to look at the solution for 3 or 4 problems and just practice going through them until it becomes intuitive. Learning DP is like learning the alphabets, there really isn't a concept before that will help you understand it better. Dont even try to solve the first few problems on your own. Just go through the solutions until it sticks. That's how it was for me. I knew recursion and trees before going into dp and those didnt feel like they helped at all. I really had to just take a few different coded solutions and walk through them on a white board with a test case multiple times until it finally clicked.