Where it runs
1. The problem
You run an ad campaign with a fixed budget, say 5,000. In front of you is a list of ad slots. Each one has a price and an expected benefit, its value. You buy a slot whole or not at all; you can't buy half a slot.
Which set of slots gives the most value without going over the budget? The first idea is to try every possible set. With 10 slots there are 1024 sets, which is fine. With 40 there are more than a trillion, and the search runs for hours.
This is the 0/1 knapsack problem, one of the DP shapes you meet most often in real work. "0/1" means each item is either taken whole (1) or left out (0).
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- best/maximum/minimum ending at position i
- ways to reach, climb, or tile
- cannot pick two adjacent items
- minimum cost path through a grid
- overlapping subproblems, same state recomputed
Looks similar, isn't
- Recursion with memoization
Memoisation fills the same table from the top, on demand. This fills it upward in a fixed order.
- Greedy (exchange argument)
Greedy commits to one choice per step. DP keeps every option until the end.
- Recursion
The recursion tells you what the transition is. The table is what makes it fast.
- DP on subsequences (LIS / LCS / edit distance)
There the state is a pair of positions in two sequences. Here one index is enough.
n states with O(1) work each gives O(n). Memory drops to O(1) when only the last states matter.
On LeetCode
Problems where each item is taken once or left, under a limit, such as splitting an array into two equal sums or reaching a target with plus and minus signs. The table is indexed by item and remaining capacity.
The capacity is half the total sum, and you ask whether some subset fills it exactly.
The numbers with a plus must add up to (total + target) / 2, so count the subsets that reach exactly that capacity.
Split the stones into two groups as close in weight as you can. A knapsack with capacity half the total finds the heaviest group that fits.
Each string costs some zeros and some ones, so the capacity has two numbers and the table gets a second capacity dimension.