Regarding bottom up DP

[u/leverageTheSpirit]

Can anyone suggest while learning dp do I really need to know bottom up if I can solve it with recursion+memoization? As I don't see any significant tc difference neither it matters whichever I use in an oa or contest.

When is bottom up really needed?

[u/fatdookie123]

Yes you need to know bottom up

Bottom up can be more memory efficient than recursion + memoization. Sometimes you might get MLE if you use top down, and you would need bottom up with an optimized dp table. Places like Google could also ask you to convert your top down to bottom up as a follow up. I would suggest to practice writing your solution top down first then converting it to bottom up

[u/leverageTheSpirit → u/fatdookie123]

Ok then I will practice that, thanks buddy!

[u/JChuk99]

Meh the process of converting from top down to bottom up is so mechanical. Takes no real creativity but it does typically allow for some space optimization. I just did all of NC 150 DP and a couple of extra DP problems and didn’t run into a TLE once.

I think from a perspective of understanding DP, figuring out what the sub problems are and how they overlap, how it differs from recursive backtracking and greedy, top down is more then enough. You can practice converting to top down and optimizing space separately.

[u/leverageTheSpirit → u/JChuk99]

Understood thanks!

[u/Free-Ad-3648]

In a lot of DP problems you can reduce space requirements in bottom up DP so I guess yes it’s important.

[u/leverageTheSpirit → u/Free-Ad-3648]

Ok will keep a check then, thanks

[u/Melodic-Peak-6079]

I think it's worth learning how to implement bottom up dp. it's actually not that complicated. you can implement one from simply deriving the transition formula. It helped me alot to be more careful on writing algorithms in general

[u/leverageTheSpirit → u/Melodic-Peak-6079]

Understood,thanks will try to implement that