0/1 Knapsack — 2D DP Table

Each item is either taken (1) or not (0). Fill a 2D table row-by-row.
Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
LC 416 (Partition Equal Subset Sum), LC 494 (Target Sum), LC 1049.

State: dp[i][w] = max value using items 0…i with capacity w.
Choice at each item:

Skip item i: dp[i-1][w] — same capacity, one fewer item.
Take item i (if w ≥ wt[i]): dp[i-1][w-wt[i]] + val[i] — use remaining capacity and add value.

Key constraint: Each item can only be taken once (0/1), so we look at the previous row dp[i-1], never the same row.

Filled cell

Current cell

Source cells

Optimal path

Controls

Items (random)

Capacity: 8 Speed

Time: O(n·W) | Space: O(n·W)

0/1 Knapsack — 2D DP Table

Controls

Steps