Dynamic Programming

State-Machine DP

Track a few named states per step (holding / not holding, cooldown) and transition between them.

Medium, about 90 minutes to practise.

1Understand

The idea

Name the few situations you can be in at each step (holding a stock or not, in cooldown or not) and keep one best value per state. Each day, every state is computed from the previous day's states through the allowed transitions, such as buying, selling or resting. Drawing the states as a diagram first makes the transitions obvious.

Intuition

Name the few situations you can be in at each step, holding stock or not, in cooldown or not, and keep one best value per state. Each day, every state updates from the previous day's states through allowed transitions (buy, sell, rest).

Drawing the states as a tiny diagram first makes the transitions obvious and prevents illegal moves (selling twice, buying during cooldown).

This is still 1-D DP; the "dimension" is the discrete state label.

What you will be able to do

  • Name each state and its transitions
  • Update states from the previous step only

When to use it

  • Buy and sell stock with a rule (cooldown, fee, k transactions)
  • Each step is in one of a few modes
  • Choices depend on what happened on the previous step

2See it

Walkthrough

Stock buy/sell states

prices = [1, 2, 4], hold vs free cash.

1 / 6

i
1
2
4
012
i → index 0

Before day 0: hold = −∞, free = 0. Buy on day 0 → hold = −1.

hold, free = -inf, 0

Live template

Line 1 active

1hold, free = -inf, 0
2for price in prices:
3 hold, free = max(hold, free - price), max(free, hold + price - fee)
4return free

Complexity: time O(n·states), space O(states)

Time O(n) (or O(n·k) with k transactions), space O(1) states. Enumerating all trade sequences is exponential. State machines scale cleanly when rules get finicky.

Read the walkthrough as text

Best time to buy/sell with cooldown. Prices [1,2,3,0,2].

  1. States: hold = max profit holding stock; sold = just sold today; rest = free to buy.
  2. Transitions: hold = max(hold, rest - price); sold = hold + price; rest = max(rest, sold).
  3. Process day by day using previous values (copy before updating).
  4. End answer max(rest, sold) = 3.

Without cooldown, two states (hold / free) suffice; with at most k transactions, index states by k.

3Recognise it

Kinds of problems (8)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Stock with one transaction

    Example. Max profit with at most one buy-sell.

    How. Track min price so far; update best sell profit in one pass.

  • Unlimited transactions

    Example. Buy and sell any times with no overlap.

    How. States hold/free: sell from hold, buy from free each day; update from previous states.

  • With cooldown

    Example. Sell then wait one day before buying again.

    How. Separate states for hold, free, cooldown; transitions only from prior-day copies.

  • With transaction fee

    Example. Pay fee on each sell.

    How. Subtract fee on sell transition; still keep hold vs free states.

  • At most k transactions

    Example. Cap the number of completed trades.

    How. Add dimension or layer for remaining transactions; compress buy/sell per layer.

  • Paint house / colouring with neighbour rules

    Example. Paint n houses with no adjacent same colour, minimum cost.

    How. dp[i][colour] = cost plus min of other colours at i−1.

  • Small per-index states with transitions (binary strings, sequences)

    Example. Count binary strings without consecutive ones.

    How. Per position states ending in 0 or 1; transition counts from previous.

  • Digit DP (count numbers up to N)

    Example. Count numbers ≤ N with a digit property.

    How. DFS on position with tight flag and leading-zero flag; memo on (pos, tight, …).

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • State overwritten mid-step

    Why it happens. Updating hold then using new hold to compute free in the same day.

    How it fails. free = max(old_free, hold+price) after hold already updated, same-day round trip counted.

    Fix. Snapshot previous hold/free; compute all new states from old_* in one pass.

  • Missing state

    Why it happens. Cooldown feels like just another “cannot buy” flag.

    How it fails. Merge cooldown into free, buy immediately after sell on banned day.

    Fix. Separate states with distinct transitions (hold, free, cooldown).

  • Greedy where rules forbid it

    Why it happens. Sum every upward run maximises profit with unlimited trades only.

    How it fails. Fee per trade: greedy capture every rise pays fee twice per round trip too often.

    Fix. Use state DP when fees, cooldown, or transaction limits apply.

  • Tight flag mishandled

    Why it happens. Tight bound feels like “still matching N” until you pick a smaller digit.

    How it fails. Digit DP stays tight after placing 3 when N has 5 at position, blocks valid larger tails.

    Fix. tight = (prefix equals N prefix); looser once digit < bound digit.

  • Leading zeros counted

    Why it happens. Zeros before the number starts look like real digits in the mask.

    How it fails. Count numbers < 100 with leading zero state counted as value 0 twice.

    Fix. Leading-zero flag: still placing prefix, not yet a valid positive number.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons