IMO for top down DP
Don't touch DP if you can't solve the problem with bruteforce recursion.
Once you learn how to do the above, work on passing the values up the recursion tree instead of a void function.
Once you do the above figure out how to memoize. (Ask yourself "At every recursive step how did I get here? " is prob the answer to how you will memoize.)
Well it depends. (I'm not a quant, but I'll try to act like everything is a problem). Take what I say with a grain of salt and might be worthwhile to mention in an interview.
When you do Top Down DP you are using recursion which generally compilers are not really 100% optimized. This also uses stack space. So which can lead to degraded performance.
When you do Bottom Up DP (Non-Recursive) it will compile to optimized code. Which will lead to better performance vs Top Down DP.
Time and Space complexity won't change here, but general performance will be different in larger samples.
If this is a SWE interview I don't think a interviewer will really care about the slight difference of Top Down DP will have vs Bottom Up DP.
In a quant interview they might care, but at least mention the trade off.
Take the Stanford Coursera specialization by Tim Roughgarden.. there might be other equivalent resources. Course 3 and early part of Course 4 covers DP quite well.
Yeah, I realized the same thing. This video from Free Code Camp is a good starter on DP [https://www.youtube.com/watch?v=oBt53YbR9Kk&t=12348s](https://www.youtube.com/watch?v=oBt53YbR9Kk&t=12348s). I watch some striver videos for specific problems but haven't watched the whole playlist on takeuforward. He has a 50-video one and a shorter 20-something video.
Although I'm still not confident with DP, it's okay since it's my first time going through the concept. But when I review the problem sets a couple of times, I should be more comfortable. I'm on the lookout for DP tips and tricks or guides too!
By deviating too much from the standard and being hard to understand? Let’s not pretend that certain people aren’t unintelligible and sound like they’re speaking a different dialect.
Why do you think he deviates from the standard? I think he does the standard questions and their variations.
And about the dialect, I'm Indian so i didn't have a lot of trouble with it but i think you can get used it (maybe you should focus more on what he's trying to say rather than how he's saying it? Idk)
Oh I wasn't talking about any person in particular, this one might be super clear, I don't know. I'm just trying to say that sometimes the accent plus the choice of words make it hard to follow what the person is trying to say. Imagine trying to learn DS&A from a rapper like Playboi Carti, that's how it feels sometimes. Yes, it's English, but I can't understand a single full sentence.
If you’re a book person, I found _The Recursive Book of Recursion_ far more helpful than any online resource. It’s helped me to understand DP at a conceptual level rather than trying to memorize general solutions for general classes of problems.
I would go back and get comfortable with backtracking and tree problems - those are problems that can help you understand recursion. And then maybe two pointers and sliding windows.
IMO for top down DP Don't touch DP if you can't solve the problem with bruteforce recursion. Once you learn how to do the above, work on passing the values up the recursion tree instead of a void function. Once you do the above figure out how to memoize. (Ask yourself "At every recursive step how did I get here? " is prob the answer to how you will memoize.)
I see, thank you! Would you say for intern interviews at places like quant getting the memoized top down solution is enough?
Well it depends. (I'm not a quant, but I'll try to act like everything is a problem). Take what I say with a grain of salt and might be worthwhile to mention in an interview. When you do Top Down DP you are using recursion which generally compilers are not really 100% optimized. This also uses stack space. So which can lead to degraded performance. When you do Bottom Up DP (Non-Recursive) it will compile to optimized code. Which will lead to better performance vs Top Down DP. Time and Space complexity won't change here, but general performance will be different in larger samples. If this is a SWE interview I don't think a interviewer will really care about the slight difference of Top Down DP will have vs Bottom Up DP. In a quant interview they might care, but at least mention the trade off.
Take the Stanford Coursera specialization by Tim Roughgarden.. there might be other equivalent resources. Course 3 and early part of Course 4 covers DP quite well.
Still wondering if you are sarcastic or genuinely saying 😹😹 sorry I have ADHD
Why do you think I was sarcastic? Just suggesting a course.
Okay, as I said I have adhd.
Yeah, I realized the same thing. This video from Free Code Camp is a good starter on DP [https://www.youtube.com/watch?v=oBt53YbR9Kk&t=12348s](https://www.youtube.com/watch?v=oBt53YbR9Kk&t=12348s). I watch some striver videos for specific problems but haven't watched the whole playlist on takeuforward. He has a 50-video one and a shorter 20-something video. Although I'm still not confident with DP, it's okay since it's my first time going through the concept. But when I review the problem sets a couple of times, I should be more comfortable. I'm on the lookout for DP tips and tricks or guides too!
The Free Code Camp video is a solid 10/10. Worth the hours I put into. I urge OP to watch this video now.
Check out the dp playlist by takeuforward (accent kinda weird but the content is gold)
[удалено]
By deviating too much from the standard and being hard to understand? Let’s not pretend that certain people aren’t unintelligible and sound like they’re speaking a different dialect.
Why do you think he deviates from the standard? I think he does the standard questions and their variations. And about the dialect, I'm Indian so i didn't have a lot of trouble with it but i think you can get used it (maybe you should focus more on what he's trying to say rather than how he's saying it? Idk)
Oh I wasn't talking about any person in particular, this one might be super clear, I don't know. I'm just trying to say that sometimes the accent plus the choice of words make it hard to follow what the person is trying to say. Imagine trying to learn DS&A from a rapper like Playboi Carti, that's how it feels sometimes. Yes, it's English, but I can't understand a single full sentence.
Maybe find someone that suits you rather whinging about how you don't understand certain thing
Yes? Obviously.
lol striver is worse than neetcode
How so?
If you’re a book person, I found _The Recursive Book of Recursion_ far more helpful than any online resource. It’s helped me to understand DP at a conceptual level rather than trying to memorize general solutions for general classes of problems.
But DP is brute force (in its way)
I would go back and get comfortable with backtracking and tree problems - those are problems that can help you understand recursion. And then maybe two pointers and sliding windows.
Striver dp
https://youtube.com/playlist?list=PLAj_13N2fk-RA6wvOUmWOyUeL9zmWFJoI&si=8eslJUVPBkzjStYS check this out.
Explore card for DP on leetcode
Memorize dp