2D DP

0/1 Knapsack

Given items with weights and values, maximize value within a weight limit. For each item: include it (value + dp[remaining weight]) or skip it (dp without it). dp[i][w] = max of taking or skipping item i at weight w.

O(n * W)

say this out loud

Each item is take or leave with a shared budget, so a table over items and capacity. In 1D I must iterate capacity downward or items get reused.

How It Works

0/1 Knapsack maximizes total value when each item can be taken at most once under a weight budget. Define dp[i][w] as the best value using the first i items with capacity w. For item i you either skip it (dp[i-1][w]) or, if it fits, take it (value[i] + dp[i-1][w - weight[i]]). Trying both and keeping the max examines all 2^n subsets implicitly in only n×W table cells.

The result is O(nW) time and, since each row reads only the previous row, O(W) space. Provided you iterate weights backward so an item is not reused within its own row. This pseudo-polynomial bound is why knapsack is tractable for moderate capacities despite subset selection being NP-hard in general.

Step-by-Step Visualization

Capacity 5, items (wt 1, val 6), (wt 2, val 10), (wt 3, val 12). dp[w] = best value at capacity w

dpall zero

1/15

Code

Java

static int knapsack(int[] weights, int[] values, int capacity) {
  int n = weights.length;
  int[][] dp = new int[n+1][capacity+1];

  for (int i = 1; i <= n; i++)
    for (int w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i-1][w]; // Skip
      if (weights[i-1] <= w)
        dp[i][w] = Math.max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1]);
    }
  return dp[n][capacity];
}

Tips & Gotchas

1dp[i][w] = max value using first i items with capacity w

2For each item: take it (if it fits) or skip it

3Can optimize to 1D by iterating capacity backwards

Practice Problems

1Partition Equal Subset Sum
2Target Sum
3Last Stone Weight II
4Ones and Zeroes

About the 2D DP Pattern

The state needs two variables, typically two indices (comparing two sequences), or a position in a grid. dp[i][j] depends on dp[i-1][j], dp[i][j-1], or dp[i-1][j-1]. Fills a 2D table.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

Climbing Stairs
Coin Change
Longest Common Subsequence
0/1 Knapsack
Edit Distance
House Robber
Longest Increasing Subsequence
Word Break

Frequently Asked Questions

Why must the 1D-space version loop capacity from high to low?

Iterating backward guarantees dp[w - weight] still holds the previous item row's value, so each item is counted at most once. Looping forward would let the current item contribute multiple times, which silently turns 0/1 knapsack into unbounded knapsack.

How do I spot a knapsack hiding inside a problem statement?

Look for a fixed budget or target (capacity, sum, count) and per-element include/exclude decisions. Partition Equal Subset Sum, for example, is knapsack with target = totalSum / 2 and a boolean 'can we hit exactly this sum' table.

Is O(nW) truly polynomial time?

It is pseudo-polynomial: W is a numeric value, so its bit-length is log W, and O(nW) is exponential in the input's encoded size. That is why knapsack is NP-hard in theory yet perfectly practical when capacities are in the thousands.