DP State Machine Interview Patterns: Buy/Sell Stock, Best Time with Cooldown, and Regex Matching (2025)

State Machine DP Pattern

State machine DP models problems as transitions between discrete states over a sequence. The key: define your states explicitly (what decisions or conditions are captured), write the transition function (how do you move between states on each input), and identify base cases. This pattern applies when: there are a small fixed number of “modes” (holding/not holding, in-cooldown/not, matched/not), transitions depend only on the current state (not history), and the optimal sub-problem depends on which state you are in. The recurrence is: dp[i][state] = optimal(transitions from dp[i-1][all states]).

Buy and Sell Stock — Multiple Transactions (LC 188)

At most k transactions. States: cash (no stock held), hold (stock held). dp[i][j][0] = max profit on day i, with j transactions completed, holding nothing. dp[i][j][1] = same but holding a stock.

def max_profit_k(k: int, prices: list[int]) -> int:
    n = len(prices)
    if n == 0 or k == 0:
        return 0
    # If k >= n//2, equivalent to unlimited transactions
    if k >= n // 2:
        return sum(max(prices[i+1] - prices[i], 0) for i in range(n-1))

    # dp[j][0] = max profit with j transactions done, not holding
    # dp[j][1] = max profit with j transactions done, holding
    dp = [[-float('inf')] * 2 for _ in range(k + 1)]
    dp[0][0] = 0

    for price in prices:
        new_dp = [[-float('inf')] * 2 for _ in range(k + 1)]
        new_dp[0][0] = 0
        for j in range(k + 1):
            # Keep not-holding or sell (complete transaction j)
            if dp[j][0] != -float('inf'):
                new_dp[j][0] = max(new_dp[j][0], dp[j][0])  # rest
            if j > 0 and dp[j-1][1] != -float('inf'):
                new_dp[j][0] = max(new_dp[j][0], dp[j-1][1] + price)  # sell
            # Keep holding or buy
            if dp[j][1] != -float('inf'):
                new_dp[j][1] = max(new_dp[j][1], dp[j][1])  # rest
            if dp[j][0] != -float('inf'):
                new_dp[j][1] = max(new_dp[j][1], dp[j][0] - price)  # buy
        dp = new_dp
    return max(dp[j][0] for j in range(k + 1))

Best Time to Buy and Sell Stock with Cooldown (LC 309)

After selling, must wait one day before buying again (cooldown). States: hold (own stock), sold (just sold, in cooldown), rest (no stock, not in cooldown — can buy). Transitions: hold → hold (do nothing), hold → sold (sell). sold → rest (mandatory cooldown). rest → rest (do nothing), rest → hold (buy).

def max_profit_cooldown(prices: list[int]) -> int:
    hold = -float('inf')  # max profit when holding stock
    sold = 0               # max profit day after selling (cooldown)
    rest = 0               # max profit when resting (can buy)

    for price in prices:
        prev_hold, prev_sold, prev_rest = hold, sold, rest
        hold = max(prev_hold, prev_rest - price)  # keep or buy
        sold = prev_hold + price                   # sell (from hold)
        rest = max(prev_rest, prev_sold)           # keep resting or exit cooldown
    return max(sold, rest)

Best Time with Transaction Fee (LC 714)

Pay fee on each sell. Two states: cash (not holding) and hold (holding stock). cash[i] = max(cash[i-1], hold[i-1] + prices[i] – fee). hold[i] = max(hold[i-1], cash[i-1] – prices[i]).

def max_profit_fee(prices: list[int], fee: int) -> int:
    cash, hold = 0, -prices[0]
    for price in prices[1:]:
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)
    return cash

Regex Matching (LC 10) — 2D State Machine DP

Match string s against pattern p with . (any char) and * (zero or more of preceding). dp[i][j] = True if s[:i] matches p[:j]. Transitions: if p[j-1] == s[i-1] or p[j-1] == ‘.’: dp[i][j] = dp[i-1][j-1]. If p[j-1] == ‘*’: zero occurrences: dp[i][j] |= dp[i][j-2]. One or more: if p[j-2] matches s[i-1]: dp[i][j] |= dp[i-1][j].

def is_match(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    # Patterns like a*, a*b*, a*b*c* can match empty string
    for j in range(2, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                dp[i][j] = dp[i][j-2]  # zero occurrences
                if p[j-2] == s[i-1] or p[j-2] == '.':
                    dp[i][j] |= dp[i-1][j]  # one or more
            elif p[j-1] == s[i-1] or p[j-1] == '.':
                dp[i][j] = dp[i-1][j-1]
    return dp[m][n]

Wildcard Matching (LC 44) with ? and *: similar DP but * matches any sequence of characters (not just one character repeated). The * transition: dp[i][j] |= dp[i-1][j] (match one more char) or dp[i][j-2] is wrong — use dp[i][j] |= dp[i-1][j] (consume one s char, stay at *) and dp[i][j] |= dp[i][j-1] (advance past * matching nothing).

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What defines a problem as a "state machine DP" problem?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A problem is a state machine DP when: (1) you make decisions over a sequence (prices, characters, items), (2) there are a small fixed number of discrete states at each step (holding/not-holding, in-cooldown/not, matched/not), (3) transitions between states depend only on the current state and current input — not on the full history (Markov property), and (4) you want to optimize an accumulated value (profit, matches). If these conditions hold, define dp[i][state] = optimal value after processing the first i elements while in <state>. Transitions: dp[i][state] = optimal over all valid previous states and the action taken at step i.”}},{“@type”:”Question”,”name”:”How do you identify the states for the buy/sell stock with cooldown problem?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The key constraint is: after selling, you cannot buy on the next day. So your "mode" on any given day is determined by what you did recently. Three states capture all relevant history: HOLD (you currently own a stock — bought on a previous day), SOLD (you just sold today — in cooldown, cannot buy tomorrow), REST (you own no stock and are not in cooldown — can buy today). From HOLD: you can stay HOLD (do nothing) or transition to SOLD (sell at today's price). From SOLD: you must go to REST (mandatory cooldown — cannot buy next day). From REST: you can stay REST (do nothing) or go to HOLD (buy at today's price). No other state transitions are valid.”}},{“@type”:”Question”,”name”:”Why does the k-transaction stock problem special-case k >= n//2?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”In a price series of n days, the maximum number of profitable non-overlapping transactions is n//2 (every other day). If k >= n//2, you have enough transactions available to take every profitable single-day move: whenever prices[i+1] > prices[i], you can buy on day i and sell on day i+1. This is equivalent to unlimited transactions and reduces to a simple greedy sum of positive differences: sum(max(prices[i+1] – prices[i], 0) for all i). Without this check, the DP with k >= n//2 still gives the correct answer, but the O(kn) time becomes O(n^2) — the special case makes it O(n).”}},{“@type”:”Question”,”name”:”How does the * operator in regex matching translate to DP transitions?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”In regex, x* means "zero or more occurrences of x". In the DP (dp[i][j] = s[:i] matches p[:j]): when p[j-1] == '*', the * applies to p[j-2] (the preceding character). Two cases: (1) Zero occurrences of p[j-2]: dp[i][j] |= dp[i][j-2] — skip both the x and * in the pattern without consuming any character from s. (2) One or more occurrences: only valid if p[j-2] matches s[i-1] (i.e., p[j-2] == s[i-1] or p[j-2] == '.'). Then: dp[i][j] |= dp[i-1][j] — consume one character from s, but keep the x* in the pattern (it can still match more characters). The "one or more" transition looks backward in s while staying at the same pattern position j.”}},{“@type”:”Question”,”name”:”What is the difference between regex matching (LC 10) and wildcard matching (LC 44) DP?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Regex (LC 10): . matches exactly one character; x* means zero or more of x (a pair). Wildcard (LC 44): ? matches exactly one character (like .); * matches any sequence of characters including empty (standalone, not paired with a preceding character). The key DP difference is the * transition: in regex, dp[i][j] for * checks dp[i][j-2] (skip x*) and dp[i-1][j] (match one more x). In wildcard, dp[i][j] for * checks dp[i][j-1] (advance past *, matching zero chars from s) and dp[i-1][j] (consume one char from s, keep * in pattern for more). The wildcard * is more powerful — it can match any substring.”}}]}