Tabulation & the Best Playlist
The Tunebox "commute mix" has a fixed budget, say a 25-minute ride. Every track has a length and a rating, and the app should pick the tracks with the highest total rating that still fit. A track is either in or out, since you can't play half of one. That one rule breaks the obvious greedy shortcuts. Tabulation answers the question for every smaller budget first, in a table, and then reads the best playlist straight out of it.
Flip memoization upside down
Memoization starts from the big question and recurses down to the small ones. Tabulation starts from the smallest questions and fills a table upward, in an order that guarantees each cell's inputs are already there. Here's last lesson's slot filler without any recursion:
Step through the table filling up, one cell at a time:
0/1 knapsack: the table
Define one cell:
best[i][w]= the highest rating you can get using only the firstitracks withwminutes to spend.
Track i has minutes and rating. For each cell there are two choices:
- skip it:
best[i - 1][w] - take it (if
minutes <= w):rating + best[i - 1][w - minutes]
Keep the larger. Row 0 (no tracks) and column 0 (no time) are all zeros.
Read the last row: with all three tracks and 6 minutes the best rating is 11. Each row only looks one row up, so you can fill it left to right, top to bottom.
Coming from Java/JS:
new int[n + 1][W + 1]arrives zero-filled. Python has no 2-D array literal. You build rows with a comprehension. The obvious shortcut is a trap:
grid = [[0] * 3] * 2
grid[0][0] = 5
print(grid)Reconstructing the choice
The table stores ratings, not playlists. To recover the tracks, walk back up
from the bottom-right cell. If best[i][w] equals best[i - 1][w], track i
wasn't needed. Otherwise it was taken: record it, and spend its minutes.
Look at what happens on a tie. If a track's row gives the same rating as the row above, the walk treats it as "not needed" and leaves it out. So when two playlists rate the same, the tracks near the end of the list are the ones dropped. That's a precise rule, and it's the tie rule your task uses.
❓ Cross-question: "Why not take the best rating-per-minute first?" It works when you may play a fraction of a track. With whole tracks, one high-ratio track can block two that are better together:
tracks = [["X", 6, 12], ["Y", 5, 9], ["Z", 5, 9]]
left, total = 10, 0
for name, minutes, rating in sorted(tracks, key=lambda t: t[2] / t[1], reverse=True):
if minutes <= left:
left -= minutes
total += rating
print(total)Rolling array: one row is enough
Row i only ever reads row i − 1. Keep a single list and overwrite it in
place. But you have to loop w downward, so that best[w - minutes] still
holds the previous row's value when you read it:
Loop upward instead, and a cell reads a value this same track already wrote:
There's only one track, so the best rating is 4. It prints 12 because Cobalt got packed three times. Fix the loop so each track is used at most once.
The saving is real: O(W) memory instead of O(n · W). The cost is that the rows are gone, so you can't reconstruct which tracks were chosen. When you need the playlist, not just its rating, keep the full table.
Memoization or tabulation?
| Memoization (top-down) | Tabulation (bottom-up) | |
|---|---|---|
| Writing it | straight from the recursive idea | you pick the table shape and fill order |
| Subproblems solved | only the ones actually reached | every cell, needed or not |
| Recursion limit | yes, about 1000 frames deep | none |
| Memory tricks | hard | rolling arrays are easy |
| Overhead per subproblem | a function call and a hash lookup | a list index |
Both are dynamic programming, and they compute the same cells. Start top-down when the recursion is obvious. Switch to a table when you hit the depth limit or need the speed or the memory.
| 0/1 knapsack | Time | Space |
|---|---|---|
| Brute force over every subset | O(2ⁿ · n) | O(n) |
| Full table | O(n · W) | O(n · W) |
| Rolling array | O(n · W) | O(W) |
| Reconstruct from the full table | O(n) | O(n) |
Idioms & real-world patterns
⚡ Advanced: "pseudo-polynomial"
O(n · W) looks polynomial, but W is a number in the input, not a count of
items. Measure track lengths in seconds instead of minutes and the table becomes
60× wider for the same playlist. Knapsack is NP-hard, and this DP is only fast
while budgets stay small.
⚡ Advanced: when the "bug" is the feature
The upward loop from the fix above lets a track be reused, and sometimes that's exactly what you want. Station idents can repeat, so looping upward solves the unbounded knapsack:
🎯 Your turn
Write best_playlist(tracks, budget). Each track is [name, minutes, rating].
Choose tracks (each at most once) with total minutes ≤ budget and the highest
total rating. Return {"rating": total_rating, "minutes": total_minutes, "tracks": names},
with names in input order.
best_playlist([["Aurora", 4, 7], ["Blink", 3, 5], ["Cobalt", 2, 4], ["Drift", 5, 8]], 9)→{"rating": 16, "minutes": 9, "tracks": ["Aurora", "Blink", "Cobalt"]}
Ties: build the full table, then walk back from the last track. A track is taken only when its row's rating differs from the row above.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green means this piece of the app is built. ✅