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 items. The obvious DP has a dimension for count: .
When is large, this is too slow. The Aliens Trick eliminates the count dimension entirely. By the end, you'll solve "exactly " problems without tracking in your DP state (the subproblem parameters). We'll work through four classic problems together.