Hacker News new | past | comments | ask | show | jobs | submit login
Ask HN: All (many?) DP problem flavors
1 point by mlevental on June 23, 2019 | hide | past | favorite | 2 comments
Is there a catalog somewhere of all, or at least many, of the different flavors of DP? I know about Clemson's[1] page but these are just the classical problems. On leetcode et al you see all sorts that are non-standard and you don't know you've run into a new flavor until you fail to solve it. Stuff like this[2]. Of course it can be argued that it's all DP and therefore there's no point in studying particular cases ("just learn the concept") but that's like saying learning trig substitutions for integrals isn't useful. Before anyone asks: yes this is for interview prep. It seems like between all of the interview prep sites/competitive programming sites there should be a taxonomy/list somewhere.

[1] https://people.cs.clemson.edu/~bcdean/dp_practice/

[2] https://www.hackerearth.com/practice/algorithms/dynamic-programming/bit-masking/tutorial/




I can see your motivation for trying to be exhaustive which makes sense if you expect to encounter all manners of tricky interview questions.

The best way I've found to deal with variations is to get a feel for the variations remembering that it's nothing special. Memoization is a much better name, and really it's nothing but caching re-usable results, so just think of what intermediates can be cached and re-used during computations. I've never really understood the fascination with the topic myself.


>Memoization is a much better name, and really it's nothing but caching re-usable results

memoization does not work for bottom up dp.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: