Knapsack and Grid Dynamic Programming

Knapsack and grid problems are dynamic programmes with two indices, so their tables are grids. The topic opens on the 0/1 knapsack, its skip-or-take recurrence and the cues that identify it, then fills the table for three parcels and walks back up the rows to recover the ones packed. A code card writes the table and a one-array version in three languages, and a gotcha shows how running that array's loop upwards packs an item twice. The topic then turns to grids: a walkthrough counts a robot's routes past a blocked cell, and an example swaps the sum for a minimum to find the cheapest route through a toll grid. A comparison shows how the order of two loops decides whether coins count as sets or as orders, and an exercise packs a carry-on bag with one array.