What this module covers: Module P-12's problems all had one dimension of state — a position in a sequence. This module adds a second: the state now depends on both a position (which items have been considered) and a resource constraint (how much capacity remains). This module covers 0/1 knapsack, its unbounded variant (which turns out to be Module P-12's Coin Change in disguise), and grid-path counting — the other common shape 2D DP takes.
The knapsack problem: given items, each with a weight and a value, and a bag with a maximum capacity, choose a subset of items maximizing total value without exceeding the capacity. The answer depends on two things at once: which items you're allowed to consider, and how much capacity you have left — one dimension alone can't capture that, so the DP table needs two: dp[i][w].
function knapsack01(weights: number[], values: number[], capacity: number): number { const n = weights.length; // dp[i][w] = max value achievable using the first i items, with capacity w remaining const dp: number[][] = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) { for (let w = 0; w <= capacity; w++) { // Option 1: don't take item i-1 — carry forward the best result without it dp[i][w] = dp[i - 1][w];
// Option 2: take item i-1, if it actually fits in the remaining capacity if (weights[i - 1] <= w) { dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]); } } }
dp[i][w] = the best value achievable considering only the first i items, with w capacity available. At each cell, there are exactly two choices, mirroring House Robber's shape from Module P-12, just now indexed by two dimensions instead of one: skip the current item (dp[i-1][w], unchanged capacity, one fewer item to consider) or take it, if it fits (dp[i-1][w - weight] + value, one fewer item to consider, capacity reduced by its weight). The critical detail that makes this "0/1" (each item used at most once): both options always move from row i to row i - 1 — once an item has been considered, it's never available again in any subsequent calculation for this same subset of items.
Change one assumption — items can be used any number of times — and the recurrence changes in exactly one, telling place: instead of stepping back to the previous row (i - 1) when taking an item, you stay on the same row (i), because the item you just took is still available to take again.
function unboundedKnapsack(weights: number[], values: number[], capacity: number): number { // dp[w] = max value achievable with capacity w, items reusable without limit const dp = new Array(capacity + 1).fill(0);
for (let w = 1; w <= capacity; w++) { for (let i = 0; i < weights.length; i++) { if (weights[i] <= w) { dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]); // dp[w - weight], NOT a separate "previous item" row } } }
return dp[capacity]; }
Look closely, and this is Module P-12's Coin Change, generalized: Coin Change is exactly unbounded knapsack where every "value" equals 1 (you're minimizing coin count, not maximizing value) and every coin denomination is reusable without limit — the same "stay on the same row/array, because reuse is allowed" structural signature. Recognizing that two problems that look unrelated on the surface (making change vs. packing a bag) share the identical underlying recurrence shape is a big part of what separates "I've memorized twelve DP problems" from "I can recognize a new problem's shape" — the actual, transferable skill this course is trying to build.
Not every 2D DP problem is a knapsack variant. Unique Paths — how many distinct ways can a robot travel from the top-left to the bottom-right of a grid, moving only right or down — uses a 2D table for a completely different reason: the state is naturally two-dimensional because the grid itself is.
function uniquePaths(rows: number, cols: number): number { // dp[r][c] = number of distinct paths from (0,0) to (r,c) const dp: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(1)); // Every cell in row 0 or column 0 has exactly 1 path: a straight line along the edge.
for (let r = 1; r < rows; r++) { for (let c = 1; c < cols; c++) { dp[r][c] = dp[r - 1][c] + dp[r][c - 1]; // arrived here either from directly above, or directly to the left } }
return dp[rows - 1][cols - 1]; }
uniquePaths(3, 3); // 6
The recurrence falls directly out of the movement rule: the only two ways to arrive at cell (r, c) are from (r-1, c) (moving down) or (r, c-1) (moving right), so the number of paths to (r, c) is simply the sum of the paths to each of those two predecessors. Note this is a sum, the same combination rule as Module P-12's Decode Ways (two independent, non-overlapping contributions), not a max or min — another instance of the same lesson: identifying whether the correct combination is max, min, or sum is inseparable from correctly defining the state in the first place.
0/1 knapsack models discrete resource allocation directly: choosing which subset of jobs/tasks to run on a server with fixed CPU/memory capacity, or which subset of assets to include in a portfolio under a fixed budget, when each option is an indivisible, one-time choice — take it whole, or don't take it at all.
Unbounded knapsack models reusable-resource allocation: making change with an unlimited coin supply (Module P-12's Coin Change, now understood as a special case rather than a standalone puzzle), or figuring out the minimum number of shipping containers of a few fixed, freely-reusable sizes needed to hold a given total volume.
Grid-path counting shows up directly in robotics and game-board pathing (how many distinct routes exist through a warehouse floor plan or a game level with only right/down movement allowed), and — with obstacles added to the grid (setting a cell's path count to zero) — models routing around blocked cells without needing a full graph-search algorithm for what's fundamentally still a grid.
2D DP appears whenever the state genuinely depends on two independent dimensions — an item/position index plus a resource constraint (knapsack), or two spatial coordinates (grid paths).
0/1 knapsack's dp[i][w] chooses the max of skipping an item (dp[i-1][w]) or taking it if it fits (dp[i-1][w-weight] + value) — each item usable at most once, since taking an item always steps back a row.
Unbounded knapsack changes exactly one thing: taking an item stays on the same row/array rather than stepping back, because the item remains available for reuse — and this exact recurrence shape is Module P-12's Coin Change, generalized.
Grid-path counting (dp[r][c] = dp[r-1][c] + dp[r][c-1]) sums contributions from valid predecessor cells, the same combination rule as Decode Ways, applied to a spatial grid instead of a string position.
Recognizing shared recurrence shapes across superficially different problems — Coin Change and unbounded knapsack, Decode Ways and grid paths — is the transferable skill dynamic programming is actually teaching, beyond any single memorized problem.
The next module, Dynamic Programming IV: LCS, LIS, Edit Distance, and Matrix Paths, covers 2D DP problems where the two dimensions are two separate input sequences being compared against each other, rather than one sequence plus a resource constraint.
Knowledge Check
In knapsack01, why does taking an item always reference dp[i - 1][...] (the previous row), rather than dp[i][...] (the current row), in both the "skip" and "take" options?
According to the module, what specific structural change distinguishes unboundedKnapsack from knapsack01, and why does that change permit item reuse?
Why does the module describe Coin Change (Module P-12) as "unbounded knapsack, generalized," rather than treating the two as unrelated problems?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
Written by Jatin Jain Saraf · Architect of SupraScan