Recap: Knapsack and Grid Dynamic Programming

Skip or take, loop downwards in one array, above plus left on a grid, and loop order decides what is counted.

Knapsack and grid problems are dynamic programmes whose state has two indices, items and capacity or row and column, so the table is a grid and each cell reads cells above and to the left. This card gathers what the topic established and where each idea was taught.

What the topic established, and which card it was on
The idea	Where
best[i][c] = max(skip, take if it fits); greedy by value per kilo took £8 where the table found £9	0/1 Knapsack: Choosing Items Under a Capacity
The table fills row by row, the answer is the last cell, and walking back up the rows recovers the items	Fill the Knapsack Table One Item at a Time
One array, looped from the full capacity down, gives the same value in O(W) space but not the items	Knapsack in Python, Java and TypeScript
Looping the one array upwards reuses an item, giving £10 for a best of £9; upwards is right only when items repeat	Running the One-Array Knapsack Loop Upwards
Grid routes add above and left; a blocked cell is 0, and one pallet cut 15 routes to 6	Count the Paths Across a Grid
A minimum in place of the sum finds the cheapest route, 8 where the cheapest next step paid 20	Grid DP Example: The Cheapest Route Through a Toll Grid
Coins outside count sets, amounts outside count orders: 4 and 9 ways to make 5	Counting Combinations vs Counting Orderings
A downward loop over five items packs a score of 20 where score per kilo packs 19	Practice: Packing a Carry-On Bag Under a Weight Limit

Every table in the topic is costed as its cells times one step per cell.

Two-index dynamic programmes and their costs

0/1 knapsack, n items, capacity W: O(n × W) time; O(W) space with one array, looped downwards; pseudo-polynomial
Unbounded knapsack and coin counts: O(W × items) time, O(W) space, looped upwards; every case
Grid of r rows and c columns: O(r × c) time, O(c) space with one row; every case
Combinations or orderings: Coins outside for sets, amounts outside for orders

Grids reappear when the two indices are positions in two strings. Sequence Dynamic Programming, the next topic, uses exactly that table to compare words and sequences.

← → move through sections and cards