Dynamic Programming21 sections · 916 units
Open in Course

What's Next

Preview of Slope Trick

Aliens Trick uses penalties and binary search. Slope Trick uses a completely different representation: the function itself. When DP functions are piecewise linear (from absolute values), we can represent them by their breakpoints.

Updates (like adding xa|x - a|) shift and add breakpoints. Heaps efficiently maintain this representation. Slope Trick is another advanced technique for specific problem structures. Learn Aliens first, then add Slope Trick to your toolkit.