Sequence and State DP

What is this?

Every problem here fails if you try to write dp[i]. Knowing which day it is does not tell you enough to decide what to do next — you also need to know whether you currently hold a stock, which digit the knight is standing on, or which city you are in. That extra fact is a dimension of the state, and adding it turns an impossible recurrence into an obvious one.

The skill is noticing the omission. The symptom is always the same: you write a recurrence, and you cannot compute it because the answer depends on something the state does not record.

💡 Fun fact: Best Time to Buy and Sell Stock III — at most two transactions — has a famously compact solution using just four running variables: the best balance after one buy, after one sell, after two buys, and after two sells. Each is updated from the one before it in a single left-to-right pass, so a problem that looks like it needs a n × 3 × 2 table collapses to O(1) space. The four variables are the state machine, written out by hand.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: when dp[position] cannot be computed, the state is missing something the future depends on. Add it as a dimension — a phase, a budget, a location — and the transitions between those phases become the recurrence.

1. Phases as a state machine

For two transactions, name the four phases explicitly:

buy1 = buy2 = float('-inf')      # balance after buying, i.e. money spent
sell1 = sell2 = 0                # balance after selling

for price in prices:
    buy1  = max(buy1,  -price)             # spend money to buy the first time
    sell1 = max(sell1, buy1 + price)       # sell the first
    buy2  = max(buy2,  sell1 - price)      # buy again using the first profit
    sell2 = max(sell2, buy2 + price)       # sell the second
return sell2

Read it as a chain: each phase can only be entered from the one before it. Updating them in order within the same loop iteration is deliberate — it allows a buy and a sell on the same day, which is harmless because that pair earns zero and never beats a real trade.

2. The state is a position on a graph

Knight Dialer counts distinct numbers of length n a knight can dial. The state is (steps taken, digit standing on), and the transitions are the knight's legal moves — a fixed adjacency list on the keypad:

dp[step][digit] = sum of dp[step-1][prev] for every prev that can jump to digit

Ten digits and n steps make it O(10n), and because each step reads only the previous one, two arrays of ten entries suffice. The graph is tiny and fixed, so the problem is really about recognising that "which digit am I on" belongs in the state.

3. Three dimensions

Maximum Vacation Days has weeks, cities and flight connections: dp[week][city] = the most vacation days achievable while being in city during week. Transitions consider staying put or flying to any connected city. It is the same shape as the knight problem with a value attached to each state rather than a count.

4. A 30-second worked example (two transactions)

prices = [3, 3, 5, 0, 0, 3, 1, 4]

price   buy1   sell1   buy2   sell2
  3      -3      0      -3      0
  3      -3      0      -3      0
  5      -3      2      -3      2
  0       0      2       2      2       ← buy1 improves to 0, buy2 to 2
  0       0      2       2      2
  3       0      3       2      5
  1       0      3       2      5
  4       0      4       2      6       ← answer 6

The two trades are buy at 0 sell at 3, then buy at 1 sell at 4 — profit 3 + 3 = 6 ✓. Notice buy2 = 2 means "after the second purchase my balance is +2", because the first trade's profit was already banked.

5. Where you'll actually meet this

• Trading systems. Position-aware optimisation with transaction limits is this exact state machine.
• Inventory and procurement. Whether you currently hold stock changes what the next decision costs.
• Route and itinerary planning. Maximum Vacation Days is multi-week travel optimisation with connection constraints.
• Game AI. Move counting over a board where the state is the piece's position and the step number.
• Workflow engines. Any process with phases where a transition is only legal from a particular preceding phase.

6. Problems in this chapter

▶ Best Time to Buy and Sell Stock III

Maximum profit with at most two transactions. Four chained phase variables updated in order.
Pattern: explicit state machine. Target: O(n) time, O(1) space.

▶ Knight Dialer

Count distinct n-digit numbers dialled by knight moves. State is (step, digit) over a fixed keypad adjacency.
Pattern: DP over a small graph. Target: O(n) time, O(1) space (ten values per step).

▶ Maximum Vacation Days

Maximise vacation days over k weeks across connected cities. dp[week][city], transitioning by staying or flying.
Pattern: three-dimensional sequence DP. Target: O(k · n²) time, O(n) space.

7. Common pitfalls 🚫

• Trying dp[i] alone. If the recurrence cannot be written, the state is short a dimension — that is the diagnostic, not a dead end.
• Updating the phase variables in the wrong order. They form a chain, and reversing it breaks the dependency.
• Initialising the buy phases to zero. They must start at negative infinity, or a spurious "buy for free" leaks into the answer.
• Forgetting that a city may have no outgoing flights. Staying put must always be a legal transition.
• Building a full n × 10 table for the knight. Two rows of ten suffice, and the modulus must be applied every step, not just at the end.
• Assuming exactly two transactions. The problem says at most two, which is why the sell phases start at zero.
• Ignoring modular arithmetic. Counting problems overflow quickly; apply the modulus inside the loop.

8. Key takeaways

1. A state must contain everything the future needs. If the recurrence will not write, add the missing fact.
2. Phases are a state machine, and the transitions between them are the recurrence.
3. Order matters within an iteration when phases feed one another.
4. Initialise to the correct identity — negative infinity for "impossible so far", not zero.
5. Small fixed graphs belong in the state. The knight's keypad is ten positions and a lookup table.
6. Roll the table — every problem here reads only the previous step.
7. Why interviewers love it: watching a candidate discover the missing dimension is one of the most informative things they see, and it is exactly what these problems are designed to provoke.

Order: Best Time to Buy and Sell Stock III → Knight Dialer → Maximum Vacation Days.