templates · Dynamic programming

Knapsack (0/1 and unbounded)

  • Pick items to reach an exact sum or capacity: "can we make", "fewest", "how many ways"
  • Each item is used at most once (0/1) or any number of times (unbounded: coins)
  • The target number is small enough to be an array index (up to about 10⁴)

0/1 knapsackUnbounded knapsack

the one rule

The invariant

After processing an item, dp[s] is the answer for sum s using only the items seen so far.

write it from memory

The template

0/1: each item once

javajava.util.*
/** 0/1 knapsack, Partition Equal Subset Sum: can some items (each used at most once) add up to exactly half? */static boolean canPartition(int[] nums) {    int total = 0;    for (int x : nums) total += x;    if (total % 2 != 0) return false;                    // an odd total can never split evenly    int target = total / 2;                              // the capacity    boolean[] dp = new boolean[target + 1];              // dp[s] = some items so far add up to exactly s    dp[0] = true;                                        // base case: take nothing    for (int x : nums) {                                 // each item once        for (int s = target; s >= x; s--) {              // DOWN: each item is used at most once            dp[s] = dp[s] || dp[s - x];                  // skip x, or take x        }    }    return dp[target];}

The sum loop goes down. Then dp[s - x] is still the value from before this item, so x is never taken twice.

fill in the blanks — only these lines change per problem

  1. line 6The target: half the total, the knapsack weight, or (total + target) / 2 for Target Sum.
  2. line 7The cell type: boolean for "can we make it", int for fewest or max value, count for ways.
  3. line 10The one line that decides 0/1 vs unbounded: loop down for once, up for reuse.
  4. line 11How skip and take combine: ||, min(.., .. + 1), max(.., .. + value) or +=.

unbounded: fewest coins

javajava.util.*
/** Unbounded knapsack, Coin Change: fewest coins for `amount`, each coin usable any number of times; -1 if impossible. */static int fewestCoins(int[] coins, int amount) {    int inf = amount + 1;                                // more coins than could ever be needed    int[] dp = new int[amount + 1];                      // dp[a] = fewest coins that make exactly a    Arrays.fill(dp, inf);    dp[0] = 0;                                           // base case: zero coins make 0    for (int coin : coins) {        for (int a = coin; a <= amount; a++) {           // UP: dp[a - coin] may already use this coin            dp[a] = Math.min(dp[a], dp[a - coin] + 1);   // skip the coin, or take one more of it        }    }    return dp[amount] >= inf ? -1 : dp[amount];}

The sum loop goes up. Now dp[a - coin] may already include this coin, which is exactly what "use it again" means.

fill in the blanks — only these lines change per problem

  1. line 6dp[0]: true, 0 coins, or 1 way. Every other cell starts at the neutral value (false, infinity, 0).

unbounded: count combinations

javajava.util.*
/** Unbounded, counting, Coin Change II: how many combinations of coins make `amount`. */static int countWays(int[] coins, int amount) {    int[] dp = new int[amount + 1];                      // dp[a] = combinations that make exactly a    dp[0] = 1;                                           // one way to make 0: take nothing    for (int coin : coins) {                             // coins outside: each combination counted once        for (int a = coin; a <= amount; a++) {            dp[a] += dp[a - coin];                       // ways without this coin + ways ending with it        }    }    return dp[amount];}

Coins in the outer loop count each combination once. Swap the loops and you count orderings instead (that is Combination Sum IV).

fill in the blanks — only these lines change per problem

  1. line 5Items outside, sums inside = combinations. Sums outside, items inside = orderings.

complexity

What it costs

time O(n × target)
For each of the n items, one pass over every sum from 0 to target, O(1) work per cell.
space O(target)
One 1D row of sums, reused for every item. The full 2D table is not needed.

watch out

Common bugs

  • Looping the sum up in 0/1 knapsack. Each item silently gets used many times.
  • Using Integer.MAX_VALUE as infinity and then adding 1: it overflows to a negative number. Use amount + 1.
  • Swapping the two loops in "count ways" and counting 1+2 and 2+1 as different.

use it

Practise it on

learn it properly