Skip to content
Hello Python
Pattern1 Practice3 Interview

State-machine DP

Represent each step with a small set of allowed states and transitions between them. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider State-machine DP when the prompt's constraints and required operations match this shape: Represent each step with a small set of allowed states and transitions between them.

Pybit demonstrates the State-machine DP decision pattern in a professional coding interview workspace.
On this page · Name Mutually Exclusive States

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

State-machine DP Code Labs

Name Mutually Exclusive States

State-machine DP represents each step with a small set of modes such as holding, sold, and resting. Each value means the best result among histories ending in exactly that mode.

List which prior modes may lead to each next mode and what action cost or reward applies. Illegal transitions must not enter the recurrence through a convenient default value.

Trace Stock State Transitions

Reference
def stock_state_trace(prices):
    rest=0;hold=float("-inf");sold=float("-inf");trace=[]
    for price in prices:
        previous_rest,previous_hold,previous_sold=rest,hold,sold
        rest=max(previous_rest,previous_sold);hold=max(previous_hold,previous_rest-price);sold=previous_hold+price
        trace.append([rest,hold,sold])
    return trace
Practice

Implement stock_state_trace(prices). Return [rest,hold,sold] after each price for one-share trading with one-day cooldown.

Public tests

  • Read every transition from prior state

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Update from the Previous Step Only

Compute all next values from saved previous values. Updating one variable in place and then using it for another transition can accidentally perform two actions in the same step.

Maximize Stock Profit with Cooldown

Reference
def max_cooldown_profit(prices):
    rest=0;hold=float("-inf");sold=float("-inf")
    for price in prices:
        previous_rest,previous_hold,previous_sold=rest,hold,sold
        rest=max(previous_rest,previous_sold);hold=max(previous_hold,previous_rest-price);sold=previous_hold+price
    return max(rest,sold)
Practice

Implement max_cooldown_profit(prices). Hold at most one share and wait one day after selling before buying.

Public tests

  • Respect mutually exclusive states

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Compress the State Vector Safely

A full table is unnecessary when every transition depends only on the previous step. Keep one value per mode, but preserve impossible states with negative infinity rather than treating them as zero profit.

Explain It in an Interview

Say: “These modes are mutually exclusive and complete. Each recurrence uses only legal previous modes, and I update simultaneously.” State initial reachable states, final acceptable states, and O(n × states × transitions) time.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the State-machine DP invariant is independent of a minor Python release.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
State-machine DP decision loopO(n)O(n)Maintain the best realized cash and best wealth while holding one share, updating them simultaneously for each price.

Space

O(1) for the focused Track Stock State with a Fee implementation.

Assumptions

  • The two states cover every legal end-of-day position. Each transition considers exactly staying or making the one legal trade into that state, so induction over days yields optimal state values and final cash.
  • The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

  1. State the precise State-machine DP invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Each state represents the best value under exactly one end condition.
  3. Transitions use only values from the previous step.
  4. Define mutually exclusive holding and cash states. Preserve this property after every transition.
  5. Update both states from the previous day rather than partially updated values. Preserve this property after every transition.

When To Use Or Avoid State-machine DP

Use It When

  • Use State-machine DP when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
  • Use it when each state represents the best value under exactly one end condition.

Choose Another Tool When

  • Avoid State-machine DP when its decision rule cannot eliminate work or preserve the required state.
  • Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Moving state without a proof

Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.

Prevent it: Write the decision rule beside the loop and verify it against Track Stock State with a Fee before optimizing.

Avoid

def max_profit_with_fee(prices, fee):
    pass

Use instead

def max_profit_with_fee(prices, fee):
    if not prices:
        return 0
    cash = 0
    hold = -prices[0]
    for price in prices[1:]:
        next_cash = max(cash, hold + price - fee)
        next_hold = max(hold, cash - price)
        cash, hold = next_cash, next_hold
    return cash

Where you will hit this: Track Stock State with a Fee(opens in a new tab)

Breaking the maintained state

Charges the fee on buy and sell, reducing every profitable transaction twice.

Prevent it: Use the public tests and preserve this state: Each state represents the best value under exactly one end condition.

Avoid

def max_profit_with_fee(prices,fee):
    if not prices:return 0
    cash=0; hold=-prices[0]-fee
    for p in prices[1:]:
        cash=max(cash,hold+p-fee); hold=max(hold,cash-p-fee)
    return cash

Use instead

def max_profit_with_fee(prices, fee):
    if not prices:
        return 0
    cash = 0
    hold = -prices[0]
    for price in prices[1:]:
        next_cash = max(cash, hold + price - fee)
        next_hold = max(hold, cash - price)
        cash, hold = next_cash, next_hold
    return cash

Where you will hit this: Track Stock State with a Fee(opens in a new tab)

Hiding Python work in the hot path

Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.

Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(n).

Avoid

def max_profit_with_fee(prices,fee):
    if not prices:return 0
    cash=0; hold=-prices[0]-fee
    for p in prices[1:]:
        cash=max(cash,hold+p-fee); hold=max(hold,cash-p-fee)
    return cash

Use instead

def max_profit_with_fee(prices, fee):
    if not prices:
        return 0
    cash = 0
    hold = -prices[0]
    for price in prices[1:]:
        next_cash = max(cash, hold + price - fee)
        next_hold = max(hold, cash - price)
        cash, hold = next_cash, next_hold
    return cash

Where you will hit this: House Robber(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.