2D DP

Unbounded Knapsack

Like 0/1 knapsack, but you can use each item unlimited times. The difference in code is subtle: iterate the weight loop FORWARD (not backward), so each item can be reused within the same row.

O(n * W)

O(W)

How It Works

Unbounded knapsack allows each item to be chosen any number of times. The state is the same as 0/1 knapsack — dp[w] is the best value at capacity w — but the transition changes subtly: after taking item i you may take it again, so dp[w] = max(dp[w], value[i] + dp[w - weight[i]]) where dp[w - weight[i]] already reflects the current item. In code, that means iterating the capacity loop forward instead of backward.

Complexity stays O(nW) time and O(W) space, since repetition is expressed through the direction of the sweep rather than extra states. Coin Change (minimum coins) and rod cutting are unbounded knapsack in disguise: unlimited copies of each denomination or cut length compete for one shared budget.

Step-by-Step Visualization

Unbounded knapsack: items can be reused

Itemwt=1, val=10

1/3

Code

Java

static int unboundedKnapsack(int[] weights, int[] values, int capacity) {
  int[] dp = new int[capacity + 1];

  for (int w = 0; w <= capacity; w++)
    for (int i = 0; i < weights.length; i++)
      if (weights[i] <= w)
        dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);

  return dp[capacity];
}

Tips & Gotchas

1Unlike 0/1 knapsack, items can be reused

2Iterate capacity forwards (not backwards) to allow reuse

3dp[w] = max value achievable with capacity w

Practice Problems

1Coin Change
2Coin Change II
3Integer Break
4Combination Sum IV
5Rod Cutting

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

What is the single code difference from 0/1 knapsack?

The direction of the inner capacity loop. Forward iteration lets dp[w - weight] include the current item, permitting reuse; backward iteration guarantees it does not. Everything else — states, base cases, final answer — is unchanged.

Why does loop order matter for counting combinations versus permutations?

With items in the outer loop and capacity inside, each combination is counted once in a fixed item order (Coin Change II). Swapping the loops so capacity is outermost counts every ordering separately, which is what Combination Sum IV wants.

When would I still keep a 2D table for unbounded knapsack?

Mostly for clarity or when you must reconstruct which items were used and how many times. For pure optimal-value queries the 1D forward-swept array is standard, since no information from older rows is ever needed.