DP State Design: State Machines and Swapped Dimensions

Most DP difficulty is in choosing the state. A good state carries exactly what the future needs: if something is missing, the recurrence is wrong; if there is too much, it is too slow. This article covers the two moves that fix most state problems: add a small dimension that the future depends on (state machines), and swap the answer with a dimension that is too large to index.

Intuition

Think of the state as a summary of the past. The state is self-contained (no hidden history) when any two histories with the same summary have identical futures. Check that property whenever you write a recurrence:

• If two histories with the same state can still diverge (one of them is holding a stock, the other is not), the state is missing information. Add it, usually as a tiny extra dimension: a flag, a counter, the last choice.
• If one dimension is enormous (capacity up to 10^9, a string of length 10^6) while the answer itself is small, index the table by the answer and store the other quantity as the value: "for each value, the minimum weight" instead of "for each weight, the maximum value".

When to use it in interviews / OAs

• A first DP attempt fails on a small example because the state forgets something (cooldowns, the previous color, how many operations are left).
• The problem has phases or modes (holding / not holding, robbed the previous house or not, swapped the previous pair or not).
• A capacity or distance is huge but values, counts or the number of items are small.

Adding a dimension: state machines

The stock-trading family is the standard example. On each day you are in one of a few modes, and each mode only allows certain actions. Write one variable per mode and update all of them from yesterday's values.

Unlimited transactions, optional fee, optional one-day cooldown after selling. Modes: holding a share, free to buy (cash), and "just sold today".

def max_profit(prices: list[int], fee: int = 0, cooldown: bool = False) -> int:
    hold, cash, just_sold = float("-inf"), 0, float("-inf")
    for p in prices:
        # every right-hand side uses yesterday's values
        hold, cash, just_sold = (
            max(hold, cash - p),  # keep holding, or buy today
            max(cash, just_sold),  # stay idle; yesterday's sale is now spendable
            hold + p - fee,  # sell today
        )
        if not cooldown:
            cash = max(cash, just_sold)  # without a cooldown the money is usable at once
    return max(cash, just_sold)

With the cooldown, buying today reads cash from yesterday, which includes sales from two days ago but not from yesterday: exactly a one-day wait, enforced by the state rather than by special cases.

At most k transactions. The mode must now also count transactions: buy[j] is the best profit while holding during the j-th transaction, sell[j] after completing j transactions.

def max_profit_k(prices: list[int], k: int) -> int:
    buy = [float("-inf")] * (k + 1)  # buy[j] = best profit holding a share in transaction j
    sell = [0] * (k + 1)  # sell[j] = best profit after completing j transactions
    for p in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j - 1] - p)
            sell[j] = max(sell[j], buy[j] + p)
    return sell[k]

Updating in place is safe here: reading today's sell[j - 1] or buy[j] only adds "sell and buy back at the same price", which never changes the profit. When k >= n / 2, the limit cannot bind and the unlimited version is faster.

Other state machines follow the same recipe: robbing houses (robbed the previous house or not), painting houses (color of the previous house), making two sequences increasing with swaps (swapped at the previous index or not).

Swapping the answer and a dimension

Refueling stops. A car must reach target; stations along the road have fuel. Minimize the number of stops. Indexing by position is hopeless when distances are large, but the number of stops is at most n. So flip it: reach[t] = the farthest position reachable using t stops. Each station is a 0/1 item, so the loop over t runs downward.

def min_refuel_stops(target: int, start_fuel: int, stations: list[list[int]]) -> int:
    # stations sorted by position: [position, fuel]
    reach = [start_fuel] + [0] * len(stations)  # reach[t] = farthest point with t stops
    for i, (pos, fuel) in enumerate(stations):
        for t in range(i, -1, -1):  # descending: each station is used at most once
            if reach[t] >= pos:  # the station is reachable with t stops
                reach[t + 1] = max(reach[t + 1], reach[t] + fuel)
    for t, far in enumerate(reach):
        if far >= target:
            return t
    return -1

Knapsack with a huge capacity. With weights and capacity up to 10^9 but small values, the usual "best value per weight" table cannot exist. Index by value instead: g[v] = the minimum weight that achieves value exactly v. The answer is the largest v whose minimum weight fits.

def knapsack_large_capacity(weights: list[int], values: list[int], cap: int) -> int:
    total = sum(values)
    INF = float("inf")
    g = [0] + [INF] * total  # g[v] = minimum weight that reaches value exactly v
    for w, v in zip(weights, values):
        for val in range(total, v - 1, -1):  # 0/1 items: descending
            if g[val - v] + w < g[val]:
                g[val] = g[val - v] + w
    return max(val for val in range(total + 1) if g[val] <= cap)

The same flip works for the longest common subsequence when one string is very long and the other short: store, for each LCS length j over a prefix of the short string, the shortest prefix of the long string that achieves it. The answer is bounded by the short length, so the table is small.

Dropping what the future does not need

The opposite move matters too. Keep only the last row when transitions read only the previous row; keep a bitmask instead of a list of used items; keep "the last element" instead of the whole sequence. If two different values of a dimension always lead to identical futures, merge them.

Complexity

Problem	Time	Space
Stocks, unlimited (fee/cooldown)	O(n)	O(1)
Stocks, at most k transactions	O(n * k)	O(k)
Refueling by number of stops	O(n^2)	O(n)
Knapsack indexed by value	O(n * sum of values)	O(sum of values)

Common pitfalls

• Missing mode: the cooldown or "transactions left" is not in the state, so the DP allows illegal action sequences. Test on the smallest counterexample you can think of.
• Updating from today's values by accident: when modes depend on each other, compute all new values from the old ones (tuple assignment or temporary variables) unless you have argued that in-place is safe.
• Bad initial values: "holding" before any purchase must be negative infinity, not 0.
• Too many states: adding the full history instead of a summary explodes the table. Ask what the future actually needs.
• Forgetting to flip back: after indexing by the answer, the final step is a search over the table (min t with reach[t] >= target, max v with g[v] <= cap).

Interview variations

• Stock problems: one transaction, unlimited, at most two or k, with cooldown, with a fee.
• House robber, including houses in a circle (solve two linear cases: without the first house and without the last).
• Paint houses with k colors: track the best and second-best previous colors to get O(n * k).
• Minimum swaps to make two sequences strictly increasing: modes "swapped at i" and "not swapped at i".
• Minimum refueling stops, tallest billboard (index by the height difference), knapsack with huge weights: answer-swapped states.