Intro

Now I'll show you one of the cleverest DP (dynamic programming) tricks: the Aliens Trick, also called WQS Binary Search (binary search on a penalty parameter) or Lagrangian Relaxation. You'll face problems where you must pick exactly $K$ items. The obvious DP has a dimension for count: $dp[i][k]$.

When $K$ is large, this is too slow. The Aliens Trick eliminates the count dimension entirely. By the end, you'll solve "exactly $K$" problems without tracking $K$ in your DP state (the subproblem parameters). We'll work through four classic problems together.