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

By /
⏱ 7 min read

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).

See also: Meta Interview Prep

See also: Atlassian Interview Prep

See also: Snap Interview Prep

Scroll to Top