DP state machines and the knapsack family

A state machine is a DP whose state is a mode

In the 1D chapter the state was a position: dp[i] was the best answer for the first i items. That works when the best answer for a prefix is all the future needs to know. Often it is not. In "buy and sell a stock" the future needs to know whether you are holding a share. In "paint houses so no two neighbours match" it needs to know what colour the last house got. The best profit of the prefix does not say either of those things, and two prefixes with the same best number can lead to different futures.

The fix is not a new idea, it is a wider state. Keep one number per mode: dp[i][mode] is the best result after the first i items while being in that mode. The modes are few (two, three, a handful), so you do not need a table: the numbers for item i depend only on the numbers for item i - 1, and a few variables carry the whole DP. Drawn as a picture, the modes are boxes and the allowed moves between them are arrows, which is why this family is called a state machine.

The second half of the chapter is the knapsack family: "choose items under a budget". There the extra information is the budget left, and the whole family turns on one tiny decision: in which direction the inner loop runs, and whether the items or the budget sit in the outer loop. Both halves use the same recipe, so here it is once.

Warm-up: House Robber is a two-mode machine

You have already solved this: houses in a row, each with some money, and you may not rob two houses that are next to each other. The earlier version kept the best total "up to house i". Here is the same problem with the modes written out. After deciding on house i you are in exactly one of two modes: skipped (you did not rob house i) or robbed (you did).

function robModes(nums) {
  let skipped = 0;         // best total when the last house looked at was skipped
  let robbed = -Infinity;  // best total when the last house was robbed; impossible before any house
  for (const x of nums) {
    [skipped, robbed] = [Math.max(skipped, robbed), skipped + x];
  }
  return Math.max(skipped, robbed);
}

The two new values are computed in one destructuring assignment so that both read the old skipped. If you wrote them as two separate statements, the second would see the first one's new value and the recurrence would be wrong. This habit matters again in the cooldown problem.

Dry run: robModes([2, 7, 9, 3, 1])

The answer is max(11, 12) = 12, from robbing the houses worth 2, 9 and 1. The same code is O(n) time and O(1) space. It is also the shape of the next problem, only with a different set of arrows.

Buy and sell a stock: one machine, many variants

You get a list of daily prices. You may buy and sell, holding at most one share at a time, and you want the largest total profit. The six well-known versions of this problem differ only in a rule about transactions: one allowed, unlimited, a cooldown day after each sale, a fee per sale, at most two, at most k. Learn them as one machine with the arrows changed, and you do not have to memorise six solutions.

Why the naive way fails. Choosing the best pair of days for a single transaction is a double loop, O(n²), and still easy. Choosing a set of non-overlapping buy and sell days for the unlimited version is a choice from a number of possibilities that grows exponentially, and plain recursion repeats the same suffix again and again. The state that repeats is tiny: the day, and whether you hold a share. That is the whole DP.

Unlimited transactions (the "II" version)

Read the new values off the picture. You are free after today if you were free yesterday and waited, or were holding yesterday and sold at today's price. You are held after today if you were holding and waited, or were free and bought at today's price.

function maxProfitUnlimited(prices) {
  let held = -Infinity; // best profit while holding a share; impossible before the first day
  let free = 0;         // best profit while holding nothing
  for (const p of prices) {
    [held, free] = [Math.max(held, free - p), Math.max(free, held + p)];
  }
  return free;
}

Dry run: prices [7, 1, 5, 3, 6, 4]

The answer is 7, which is (5 − 1) + (6 − 3). The machine never decided in advance which days to trade on; it kept the best value for each mode and let the last day pick. It runs in O(n) time and O(1) space.

One transaction (the "I" version)

Now you may buy once and sell once. The only change is on the buying arrow: you can no longer buy from a free mode that has already earned something, because a second purchase would be a second transaction. Before the one purchase you have earned exactly 0, so the buying arrow starts from a constant 0 and not from free.

function maxProfitOnce(prices) {
  let held = -Infinity; // best profit holding the one share we may buy
  let free = 0;         // best profit after selling it, or 0 if we never trade
  for (const p of prices) {
    [held, free] = [Math.max(held, -p), Math.max(free, held + p)];
  }
  return free;
}

On [7, 1, 5, 3, 6, 4] the held column becomes −7, −1, −1, −1, −1, −1 (the cheapest price seen so far, negated) and free becomes 0, 0, 4, 4, 5, 5. The answer is 5. This is the "track the minimum so far" loop you may know, seen as a machine: -held is that minimum.

A fee on every transaction

Each sale costs a fixed fee. Put the fee on the selling arrow: selling now gives price - fee instead of price. The fee is paid once per transaction, so it belongs on one of the two arrows, not on both.

function maxProfitWithFee(prices, fee) {
  let held = -Infinity;
  let free = 0;
  for (const p of prices) {
    [held, free] = [Math.max(held, free - p), Math.max(free, held + p - fee)];
  }
  return free;
}

Dry run: prices [1, 3, 2, 8, 4, 9] with fee 2

The answer is 8: buy at 1 and sell at 8 for 7 − 2 = 5, buy at 4 and sell at 9 for 5 − 2 = 3. The machine had to refuse the small rise on day 2, because that trade would have earned nothing after the fee. A rule like "add up every rise" does not carry over to the fee version without changes, but the machine does, because only one arrow changed.

A cooldown day after each sale: a third mode

After you sell you must wait one full day before buying again. "I sold yesterday" is now a fact the future needs, and neither free nor held remembers it. So add a mode. There are three: held, sold (you sold today, so tomorrow you cannot buy), and rest (you hold nothing and may buy tomorrow).

function maxProfitCooldown(prices) {
  let held = -Infinity; // holding a share
  let sold = -Infinity; // sold today, must rest tomorrow
  let rest = 0;         // holding nothing and free to buy
  for (const p of prices) {
    [held, sold, rest] = [Math.max(held, rest - p), held + p, Math.max(rest, sold)];
  }
  return Math.max(sold, rest);
}

Read the three new values from the arrows pointing into each box. held comes from held (wait) or from rest (buy). sold comes only from held (sell). rest comes from rest (wait) or from sold (the cooldown day passing). The answer takes max(sold, rest) because ending in held wastes the share.

Dry run: prices [1, 2, 3, 0, 2]

The answer is max(3, 2) = 3: buy at 1, sell at 2, rest on day 3, buy at 0, sell at 2, for 1 + 2. Selling on day 3 instead earns 2, but then day 4 is the forced rest day and the cheap price of 0 cannot be used.

At most two, or at most k, transactions

With a limit on the number of transactions the counter joins the state: you need to know how many you have used. Make one pair of modes for each count. Let held[j] be the best profit while holding a share that was bought as the j-th transaction, and free[j] the best profit holding nothing after at most j sales. Selling as the j-th transaction goes from held[j] to free[j]; buying the j-th goes from free[j - 1] to held[j], and free[0] is 0. For at most two transactions, unroll the loop over the counts and you have four variables:

function maxProfitTwice(prices) {
  let held1 = -Infinity, free1 = 0;
  let held2 = -Infinity, free2 = 0;
  for (const p of prices) {
    held1 = Math.max(held1, -p);
    free1 = Math.max(free1, held1 + p);
    held2 = Math.max(held2, free1 - p);
    free2 = Math.max(free2, held2 + p);
  }
  return free2;
}

This code does reuse the new free1 inside held2, which breaks the "read yesterday" rule above. It is still correct, and the reason is worth saying out loud. The new free1 may include a sale made today, and held2 then buys today, so the machine has sold and bought on the same day. That pair of trades earns exactly 0 and can be deleted from the plan, which leaves a plan with fewer transactions. The recurrences were defined as "at most", so such a plan is allowed and the value is real.

Dry run: prices [3, 3, 5, 0, 0, 3, 1, 4]

The answer is 6: buy at 0 and sell at 3 for 3, then buy at 1 and sell at 4 for 3. Day 4 is where the second transaction becomes useful: held2 = free1 - 0 = 2 means "already earned 2 from the first trade, and own a share bought for nothing".

The general version loops over the counts. Two details decide whether it passes. First, k can be far larger than the number of days, and a transaction needs two days, so at most floor(n / 2) transactions are ever useful. When k is at least that, the limit does not bind and the unlimited machine gives the answer; without this check an input with k = 109 would try to allocate a billion slots. Second, the counts are an inner loop of k steps per day.

function maxProfitK(k, prices) {
  const n = prices.length;
  if (k === 0 || n < 2) return 0;
  if (k >= Math.floor(n / 2)) return maxProfitUnlimited(prices);

  const held = new Array(k + 1).fill(-Infinity);
  const free = new Array(k + 1).fill(0);
  for (const p of prices) {
    for (let j = 1; j <= k; j++) {
      held[j] = Math.max(held[j], free[j - 1] - p);
      free[j] = Math.max(free[j], held[j] + p);
    }
  }
  return free[k];
}

Time is O(n · min(k, n/2)) and space is O(min(k, n/2)). The two-transaction function above is this one with k = 2 written out, and the same remark about buying and selling on one day applies to it. The one, unlimited, fee and cooldown versions are the same machine with the arrows changed, and the table below puts them side by side.

Paint House: the mode is the colour of the last house

Each house is painted red, blue or green, with a cost for each colour on each house, and two neighbouring houses must not share a colour. Find the cheapest way to paint them all. The best cost of the first i houses does not tell you what you can do for house i + 1, because the cheapest prefix may end in the very colour you now need to avoid. So make the colour the mode: cost[c] is the cheapest way to paint the houses so far with the last one in colour c.

function paintHouse(costs) {
  let red = 0, blue = 0, green = 0;
  for (const [r, b, g] of costs) {
    [red, blue, green] = [
      r + Math.min(blue, green),
      b + Math.min(red, green),
      g + Math.min(red, blue),
    ];
  }
  return Math.min(red, blue, green);
}

The arrows are "any colour except my own": each new colour value is that house's cost plus the cheaper of the other two previous values. Once again all three read the previous row, hence the single assignment.

Dry run: costs [[17, 2, 17], [16, 16, 5], [14, 3, 19]]

The answer is min(21, 10, 37) = 10: blue, green, blue for 2 + 5 + 3. O(n) time, O(1) space.

With k colours the same idea costs O(n · k²) if each colour scans the others. To get O(n · k), notice that a colour needs "the best previous value excluding my own colour". Keep the smallest previous value, which colour gave it, and the second smallest. A colour that is not the smallest's colour takes the smallest; the smallest's own colour takes the second smallest.

function paintHouseK(costs) {
  if (costs.length === 0) return 0;
  const k = costs[0].length;
  let prev = costs[0]; // the first house has no neighbour to avoid
  for (let i = 1; i < costs.length; i++) {
    let min1 = Infinity, min2 = Infinity, minColor = -1;
    for (let c = 0; c < k; c++) {
      if (prev[c] < min1) {
        min2 = min1;
        min1 = prev[c];
        minColor = c;
      } else if (prev[c] < min2) {
        min2 = prev[c];
      }
    }
    prev = costs[i].map((cost, c) => cost + (c === minColor ? min2 : min1));
  }
  return Math.min(...prev);
}

If two colours tie for the smallest, the second one lands in min2 through the else if, so the tie is handled. With one colour and more than one house the answer is Infinity, which is the honest answer: it cannot be done. O(n · k) time, O(k) space.

0/1 knapsack, and why the inner loop runs backwards

The second half of the chapter starts from a problem you met in the 2D chapter. You have n items, each with a weight and a value, and a bag that holds capacity weight. Each item can be taken at most once. Maximise the total value. Greedy by value per weight fails: with capacity 50 and items (weight 10, value 60), (20, 100), (30, 120), the best ratio picks the first two for 160, but the second and third make 220. Trying every subset is 2ⁿ, so the DP is the answer.

The 2D table was dp[i][w]: the best value using only the first i items with capacity w. Each row is computed from the row above it:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1])

Notice that row i never looks at row i - 2 or older. So one array is enough, if each pass over the items turns the previous row into the next row in place. Whether that works depends entirely on the order in which the cells of the pass are visited.

function knapsack01(weights, values, capacity) {
  const best = new Array(capacity + 1).fill(0); // best[w]: best value with room w, items so far
  for (let i = 0; i < weights.length; i++) {
    for (let w = capacity; w >= weights[i]; w--) { // backwards: high w first
      best[w] = Math.max(best[w], best[w - weights[i]] + values[i]);
    }
  }
  return best[capacity];
}

The proof that the direction is not a style choice

Call the array's content row i before the pass for item i begins, meaning best[w] equals the 2D value dp[i][w] for every w. We need it to equal dp[i+1][w] afterwards.

The new value at w needs two old values: dp[i][w], which is sitting in best[w], and dp[i][w - wt], which is sitting in best[w - wt], provided that cell still holds row i. The backward loop makes that true. When the loop is at index w, it has written only indices greater than w (it started at the top and has been counting down). The cell w - wt is below w, since wt is at least 1, so it has not been touched in this pass and still holds row i. (A weight of 0 reads the very cell it is about to write, and the read happens first.) The value written is therefore exactly dp[i+1][w]. Cells below wt are never written, and they should not change, because the item does not fit in so little room. After the pass the array is row i + 1, and the argument repeats for the next item.

Now run the loop the other way, from w = wt up to capacity. At index w the cell w - wt is below it, so it has already been written in this pass: it holds row i + 1, a state in which item i may already be in the bag. Reading it and adding the item's value takes the item a second time. The forward loop computes new[w] = max(old[w], new[w - wt] + value), and that is a different problem, in which each item can be used any number of times. That problem has a name and a chapter section of its own, below.

Dry run: weights [1, 3, 4, 5], values [1, 4, 5, 7], capacity 7

The array after each item, with columns for w = 0 to 7. The first row is the start.

The answer is best[7] = 9, from the items of weight 3 and 4 (4 + 5). Look at the weight-1 row: with capacity 2 the value is still 1, because the one item of weight 1 cannot be taken twice. Hold on to that cell: in the unbounded version below it becomes 2.

To see the bug rather than believe the proof, take a single item of weight 3 and value 5 and a capacity of 9. Run the loop upwards and you get a "best" of 15, three copies of an item that exists once.

function knapsackForwardBug(weights, values, capacity) {
  const best = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = weights[i]; w <= capacity; w++) { // WRONG direction for 0/1
      best[w] = Math.max(best[w], best[w - weights[i]] + values[i]);
    }
  }
  return best[capacity];
}

console.log(knapsack01([3], [5], 9));        // 5
console.log(knapsackForwardBug([3], [5], 9)); // 15

Cost. The loops do n passes of up to capacity steps: O(n · C) time and O(C) space, against O(n · C) space for the 2D table. This is pseudo-polynomial: the running time depends on the value of C, not on the number of bits needed to write it. A capacity of 10⁹ is a one-line input and a billion-cell array, so check the constraints before you choose this DP.

Unbounded knapsack: the forward loop on purpose

Now each item may be used any number of times (coins in a till, rod pieces, any "reusable choice"). The last section showed that the upward loop reads new[w - wt], a row in which the item may already be in the bag. That is exactly the rule here: "best value with room w using the items so far, each as often as I like" equals the best of leaving the item out or taking one copy and solving the smaller bag with the same freedom.

function unboundedKnapsack(weights, values, capacity) {
  const best = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = weights[i]; w <= capacity; w++) { // forwards: reuse is the point
      best[w] = Math.max(best[w], best[w - weights[i]] + values[i]);
    }
  }
  return best[capacity];
}

The code differs from knapsack01 in the direction of the inner loop and in nothing else. On the items of the last dry run the array becomes 0 1 2 4 5 7 8 9, against 0 1 1 4 5 7 8 9 before. The first difference is at w = 2: two copies of the weight-1 item are allowed now.

Time O(n · C), space O(C). For a pure maximum or minimum, the unbounded version also works with the two loops swapped (capacity outside, items inside), which is how the earlier Coin Change was written. For counting the loop order changes the answer, and the next-but-one section is about exactly that.

Bounded knapsack: split the counts into powers of two

Between the two extremes: item i exists c times. One fix is to turn it into c separate 0/1 items, which costs O(Σcᵢ · C). With counts of 10⁴ that is far too slow, and it is wasteful: you do not need c separate items, only enough pieces that every count from 0 to c can be built from a subset of them.

Split c into 1, 2, 4, 8, ... and a remainder. Pick k so that 1 + 2 + ... + 2^k−1 = 2^k − 1 is at most c and the next power would overshoot, and let the remainder be r = c − (2k − 1), which is less than 2^k. Every count t from 0 to c is a subset sum of the pieces. If t ≤ 2k − 1, binary writes it with the powers alone. Otherwise take the remainder piece r and write t − r with the powers: t − r is at most c − r = 2k − 1, and it is positive because t exceeds 2k − 1, which is at least r. No subset of the pieces sums to more than c, because the pieces add up to exactly c. For c = 13 the pieces are 1, 2, 4 and 6, and each of 0 to 13 is a sum of some of them (12 = 2 + 4 + 6, 13 = 1 + 2 + 4 + 6).

function boundedKnapsack(items, capacity) {
  const best = new Array(capacity + 1).fill(0);
  for (const { weight, value, count } of items) {
    let left = count;
    for (let piece = 1; left > 0; piece *= 2) {
      const take = Math.min(piece, left);
      left -= take;
      for (let w = capacity; w >= take * weight; w--) { // each piece is one 0/1 item: backwards
        best[w] = Math.max(best[w], best[w - take * weight] + take * value);
      }
    }
  }
  return best[capacity];
}

Each piece is a 0/1 item of weight take * weight and value take * value, so the backward loop is the one from the 0/1 section. Time is O(Σ log cᵢ · C), space O(C).

Coin Change II: the loop order decides what you count

Count the ways to make amount from unlimited coins of given values. The 1D chapter solved "fewest coins", where order of the loops did not matter. For counting it matters, and one swap turns "combinations" into "sequences". Both versions below are short, both look plausible, and they give different numbers for the same input.

function coinChangeII(amount, coins) { // counts combinations: 2 + 1 and 1 + 2 are the same way
  const ways = new Array(amount + 1).fill(0);
  ways[0] = 1;
  for (const coin of coins) {              // coins OUTSIDE
    for (let a = coin; a <= amount; a++) {
      ways[a] += ways[a - coin];
    }
  }
  return ways[amount];
}

function countOrderedSequences(amount, coins) { // counts sequences: 2 + 1 and 1 + 2 are different
  const ways = new Array(amount + 1).fill(0);
  ways[0] = 1;
  for (let a = 1; a <= amount; a++) {          // amount OUTSIDE
    for (const coin of coins) {
      if (coin <= a) ways[a] += ways[a - coin];
    }
  }
  return ways[amount];
}

console.log(coinChangeII(5, [1, 2, 5]));          // 4
console.log(countOrderedSequences(5, [1, 2, 5])); // 9
console.log(coinChangeII(4, [1, 2, 3]));          // 4
console.log(countOrderedSequences(4, [1, 2, 3])); // 7

Why the coins-outside loop counts combinations. Let W_k[a] be the number of ways to make a using only the first k kinds of coin, where a "way" is a multiset (the order is not recorded). Take the k-th kind, value c. A multiset either uses no coin of this kind, giving W_{k−1}[a] ways, or uses at least one: remove one such coin and what is left is a multiset for a − c that may still use this kind, giving W_k[a − c]. So W_k[a] = W_{k−1}[a] + W_k[a − c]. That is exactly the forward loop: ways[a] still holds W_{k−1}[a] when it is updated, and ways[a - c] was already updated and holds W_k[a − c]. Because all the coins of one kind are handled in one pass, a way can only be "extended" by kinds in the order of the outer loop, so each multiset is produced once, in one canonical order: all the 1s, then the 2s, then the 5s.

Dry run: coinChangeII(5, [1, 2, 5])

The four ways to make 5 are 5; 2+2+1; 2+1+1+1; 1+1+1+1+1. After the coin 1 there is one way to make every amount (all ones). The coin 2 adds the ways that use at least one 2.

Why the amount-outside loop counts sequences. Now ways[a] is computed as the sum over every coin c that could be the last coin: ways[a] = Σ ways[a − c]. Each sequence has exactly one last coin, so each sequence is counted once, and two orders of the same coins have different last coins or different earlier parts. For amount 5 with [1, 2, 5] the nine sequences are the 4 combinations above, expanded into their orders: {5} has 1 order, {2, 2, 1} has 3, {2, 1, 1, 1} has 4 and {1, 1, 1, 1, 1} has 1, and 1 + 3 + 4 + 1 = 9.

Dry run: countOrderedSequences(5, [1, 2, 5])

Subset sum and Partition Equal Subset Sum

Subset sum asks: can some of these numbers, each used at most once, add up to exactly target? It is the 0/1 knapsack with the value thrown away and the question turned into a yes or no, so each cell becomes a boolean: reach[s] is true if some subset of the numbers so far sums to s. The array starts with only reach[0] = true (the empty subset), and the inner loop runs backwards for the same reason as before.

function canMakeSum(nums, target) {
  if (target < 0) return false;
  const reach = new Array(target + 1).fill(false);
  reach[0] = true;
  for (const x of nums) {
    for (let s = target; s >= x; s--) {
      if (reach[s - x]) reach[s] = true;
    }
  }
  return reach[target];
}

Partition Equal Subset Sum: can the array be split into two groups with equal sums? If the total is odd, no. Otherwise one group sums to total / 2 if and only if the other does too, so the question is exactly canMakeSum(nums, total / 2).

function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  return canMakeSum(nums, total / 2);
}

Dry run: canPartition([1, 5, 11, 5])

The total is 22, so the target is 11. Columns are the reachable sums 0 to 11 (1 means reachable) after each number.

Sum 11 is reachable, from the single number 11 (the other group is 1 + 5 + 5). O(n · S) time and O(S) space, where S is the target.

A JavaScript aside: a bitset in one BigInt. The array of booleans is a bit pattern in disguise. Store it in one BigInt whose bit s means "sum s is reachable". Taking number x or not is reach | (reach << x): every reachable sum also yields that sum plus x. Because a shift builds a new value, there is no loop direction to get wrong. The mask keeps the number from growing past the target.

function canPartitionBits(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const target = BigInt(total / 2);
  const keep = (1n << (target + 1n)) - 1n; // bits 0..target only
  let reach = 1n;
  for (const x of nums) reach = (reach | (reach << BigInt(x))) & keep;
  return ((reach >> target) & 1n) === 1n;
}

It is the same recurrence with a different container, so it has the same O(n · S) bit operations. Treat it as a neat alternative to know about, and measure before claiming it is faster on a given input.

Target Sum: signs become a subset count

Put a + or - in front of every number so that the expression equals target, and count how many sign assignments do. Trying all signs is 2ⁿ, and a recursion over (index, running sum) repeats states, but there is a better move: reduce it to a different question.

Let P be the sum of the numbers that got a + and N the sum of those that got a -. Then P − N = target and P + N = total. Add the two equations: 2P = total + target. So P = (total + target) / 2, and the question becomes how many subsets of the numbers sum to P, a counting subset sum. Each subset of positions is exactly one sign assignment, so the count is the same, and two equal values at different positions count separately, as they should.

Two cases have no answer: |target| > total (the expression cannot reach that far), and total + target odd (P would not be a whole number). Check both before building an array, which also keeps P non-negative.

function findTargetSumWays(nums, target) {
  const total = nums.reduce((a, b) => a + b, 0);
  const shifted = total + target;
  if (Math.abs(target) > total || shifted % 2 !== 0) return 0;
  const want = shifted / 2;
  const ways = new Array(want + 1).fill(0);
  ways[0] = 1;
  for (const x of nums) {
    for (let s = want; s >= x; s--) ways[s] += ways[s - x];
  }
  return ways[want];
}

Dry run: findTargetSumWays([1, 1, 2, 3], 1)

The total is 7, so P = (7 + 1) / 2 = 4. Columns are ways[0..4].

The answer is 3. The subsets with sum 4 are {first 1, 3}, {second 1, 3} and {1, 1, 2}. In sign form the numbers in the subset get a plus and the rest a minus: +1 −1 −2 +3, −1 +1 −2 +3 and +1 +1 +2 −3 all equal 1.

Ones and Zeroes: a knapsack with two budgets

You get binary strings, and you may use at most m zeros and n ones in total. Choose the largest number of strings you can afford. Each string is an item that costs some zeros and some ones and has the value 1; each item can be used once. That is the 0/1 knapsack with a budget of two numbers, so the array has two axes: best[z][o] is the most strings that fit within z zeros and o ones.

The proof of the backwards loop does not care how many axes there are, only that the cell you read must still hold the previous item's value. Cell [z - zeros][o - ones] is "before" cell [z][o] in both axes, so run both loops from high to low.

function findMaxForm(strs, m, n) {
  const best = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (const s of strs) {
    let zeros = 0;
    for (const ch of s) if (ch === "0") zeros++;
    const ones = s.length - zeros;
    for (let z = m; z >= zeros; z--) {
      for (let o = n; o >= ones; o--) {
        best[z][o] = Math.max(best[z][o], best[z - zeros][o - ones] + 1);
      }
    }
  }
  return best[m][n];
}

Dry run: findMaxForm(["10", "0", "1"], 1, 1)

The grid best[z][o] for z, o in {0, 1}, written as rows of z. The string "10" costs one zero and one one, "0" costs one zero, "1" costs one one.

The answer is best[1][1] = 2: take "0" and "1", which together fit the budget, and skip "10", which would use the whole budget for one string. Time O(L · m · n) for L strings plus the cost of counting characters, space O(m · n).

Last Stone Weight II: a partition problem in disguise

You have stones with positive weights. Repeatedly pick any two, smash them together, and put back a stone of weight |x − y| (or nothing if they are equal). What is the smallest possible weight of the last stone? This is not the heap problem where you must smash the two heaviest stones: here you choose which two, and heaviest-first can be beaten. On [3, 3, 2, 2, 2] smashing the two heaviest each time ends with a stone of 2, while splitting the stones into {3, 3} and {2, 2, 2} reaches 0.

Derive the reduction. A smash replaces x and y by their difference, which is x with y subtracted. Follow all the smashes through to the end: every original stone has been added or subtracted exactly once (by induction, each smash combines two signed sums into their difference), so the last stone is the absolute value of some signed sum Σ ± stone. A signed sum splits the stones into a group with + and a group with -, and its size is the gap between the two group sums. So the last weight is at least the smallest gap over all ways to split the stones into two groups.

The bound is reached. Take a split with the smallest gap D. If one group is empty (the gap is the whole total), move a single stone across: the gap becomes |total − 2y|, no larger, so a best split with both groups non-empty exists when there are at least two stones. Smash one stone x from the heavier group A against one stone y from the lighter group B and put the leftover |x − y| into the group of whichever stone was larger. That group loses the smaller of the two weights, and so does the other one, so the gap between the group sums is still D and there is one stone fewer. Repeat on the smaller set (the base case is a single stone, whose weight is the gap with an empty other group). Since no result can be below D and one smash order reaches D, the smallest last stone is exactly D.

So the answer is the smallest gap, which is a subset sum problem: find the largest s ≤ total / 2 that some subset sums to, and the gap is total − 2s.

function lastStoneWeightII(stones) {
  const total = stones.reduce((a, b) => a + b, 0);
  const half = Math.floor(total / 2);
  const reach = new Array(half + 1).fill(false);
  reach[0] = true;
  for (const stone of stones) {
    for (let s = half; s >= stone; s--) {
      if (reach[s - stone]) reach[s] = true;
    }
  }
  let best = half;
  while (!reach[best]) best--;
  return total - 2 * best;
}

Dry run: lastStoneWeightII([2, 7, 4, 1, 8, 1])

The total is 23, so half = 11. Columns are the reachable sums 0 to 11.

After the stone 1, every sum up to 11 is reachable, and the remaining stones (8 and 1) change nothing in this range. The largest reachable sum is 11, so the answer is 23 − 2 · 11 = 1: one group sums to 11, the other to 12. Time O(n · total), space O(total).

Choosing the loop: one table for the whole family

Everything in the second half is one skeleton, a 1D array over the budget, with two switches: the direction of the inner loop over the budget, and which loop is outside.

Recognizing the shape in an unseen problem

• "You may not do X two steps in a row", "after Y you must wait": the constraint talks about the previous step. Make the previous step's kind the mode.
• "At most k of something" together with positions or days: add the counter to the state, one pair of modes per count, and cap k by what the input allows.
• "Neighbours must differ" with a few choices each (colours, flavours): the mode is the choice made last.
• A list of numbers or items, each used once, and a target or a limit: 0/1 knapsack. If the target is "exactly equal", the array is boolean or a count and starts from [0] = true or 1.
• "Split into two groups with equal or nearly equal sums", "assign plus and minus": rewrite it as a subset sum to total / 2 or to (total + target) / 2.
• "Unlimited supply" of each item: the forward loop. "Number of ways": ask whether order counts, and place the loops accordingly.
• Two limits at once (zeros and ones, weight and volume): one more axis on the array, and both loops run backwards.
• The budget is huge (10⁹) but the number of items is small: this DP is the wrong tool, because its cost depends on the value of the budget.