Dynamic Programming21 sections · 916 units
Open in Course

What's Next

Preview of Aliens Trick

Monotonic queue optimizes DP with window constraints. But some DPs have a different constraint: "use exactly kk elements". Aliens Trick (WQS Binary Search) handles this.

Instead of fixing kk, we add a penalty λ\lambda per element and binary search on λ\lambda. The idea: with the right penalty, the unconstrained optimum naturally uses exactly kk elements. This is a effective meta-technique. It transforms constrained problems into simpler unconstrained ones.