State-machine dynamic programming

Overview

State-machine DP adds a small 'mode' to the DP state: for example, whether you currently hold a stock, whether you are in cooldown, or how many transactions you have used. At each step you compute the best value for every mode from the previous step's modes, following the allowed transitions between them.

The stock problems are the classic family. With modes hold and cash, today's hold = max(yesterday's hold, yesterday's cash - price), and today's cash = max(yesterday's cash, yesterday's hold + price). Adding cooldowns, fees, or transaction limits just adds modes or transitions.

When to use it

• Rules depend on what you did previously: holding, cooldown, last action.
• A limited number of transactions or actions.
• Alternating or pattern constraints on sequences (last character type, parity).
• You can draw the problem as a few states with arrows labeled by actions.

Problem patterns it solves

Where it is used in real software

Key terms

Mode / state

A small label describing the situation, such as hold or cash.

Transition

An allowed move between modes with its reward or cost.

Viterbi

State-machine DP for the most likely sequence of hidden states.

Rolling states

Keep only the previous step's value for each mode.

Designing a state machine DP

1. 1
   List the modes

   Stock with cooldown: hold, sold (just sold today), rest (free to buy).

2. 2
   Draw the transitions

   rest -> hold (buy), hold -> sold (sell), sold -> rest (cooldown), and each can stay.

3. 3
   Write one equation per mode

   hold = max(hold, rest - price); sold = hold + price; rest = max(rest, sold).

4. 4
   Initialize

   hold = -Infinity (cannot hold before buying), sold = -Infinity, rest = 0.

5. 5
   Answer

   The best among modes where you do not hold a stock: max(sold, rest).

Stock with cooldown on prices [1, 2, 3, 0, 2]

Use previous-day values when updating each mode

Answer max(sold, rest) = 3: buy at 1, sell at 2, cooldown, buy at 0, sell at 2. The cooldown is enforced because hold can only come from rest, never directly from sold.

Implementation

1// 122. Unlimited transactions2function maxProfitII(prices) {3  let hold = -Infinity, cash = 0;4  for (const p of prices) {5    const prevHold = hold;6    hold = Math.max(hold, cash - p);7    cash = Math.max(cash, prevHold + p);8  }9  return cash;10}11 12// 309. With cooldown13function maxProfitCooldown(prices) {14  let hold = -Infinity, sold = -Infinity, rest = 0;15  for (const p of prices) {16    const [h, s, r] = [hold, sold, rest];17    hold = Math.max(h, r - p); // buy only from rest18    sold = h + p;              // sell today19    rest = Math.max(r, s);     // cooldown passes20  }21  return Math.max(sold, rest);22}23 24// 714. With transaction fee25function maxProfitFee(prices, fee) {26  let hold = -prices[0], cash = 0;27  for (const p of prices.slice(1)) {28    hold = Math.max(hold, cash - p);29    cash = Math.max(cash, hold + p - fee);30  }31  return cash;32}33 34// 188. At most k transactions: modes per transaction count35function maxProfitK(k, prices) {36  const buy = new Array(k + 1).fill(-Infinity);37  const sell = new Array(k + 1).fill(0);38  for (const p of prices) {39    for (let t = 1; t <= k; t++) {40      buy[t] = Math.max(buy[t], sell[t - 1] - p);41      sell[t] = Math.max(sell[t], buy[t] + p);42    }43  }44  return sell[k];45}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Reading an already-updated mode in the same step.

  Fix: Save previous values before computing the new ones.

• Initializing hold to 0.

  Fix: Holding a stock before buying is impossible: use -Infinity (or -prices[0]).

• k larger than n / 2 in the k-transactions problem.

  Fix: Then it equals unlimited transactions; switch to the O(n) version to avoid huge loops.

Interview questions

Practice problems