3 ms·
Ask HN: All (many?) DP problem flavors
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/
- karmakaze 7y agoI 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.
- mlevental 7y ago>Memoization is a much better name, and really it's nothing but caching re-usable results memoization does not work for bottom up dp.