DP: State Machines & Intervals

The stock problems as state machines, and interval DP by choosing what happens last.

Two kinds of DP problems trip up candidates who are comfortable with 1D and 2D tables. State-machine DP tracks *which situation you're in* (holding a stock or not, on cooldown or not). Interval DP asks *which element to handle last* inside a range. Both become manageable once you name the states explicitly.

State-machine DP

Some problems have a small number of modes at each step, with rules about moving between them. Make each mode a DP variable, and write one transition per arrow.

The stock problems

All six "best time to buy and sell stock" problems are one state machine with different rules:

(Holding) -> [sell] -> (Cooldown) -> [wait] -> (Free) -> [buy] -> (Holding)
(Holding) -> [hold] -> (Holding)
(Free) -> [rest] -> (Free)

def max_profit_cooldown(prices):
    hold, cool, free = float("-inf"), 0, 0
    for p in prices:
        hold, cool, free = (
            max(hold, free - p),      # keep holding, or buy today
            hold + p,                 # sell today → cooldown tomorrow
            max(free, cool),          # rest, or come out of cooldown
        )
    return max(cool, free)

Every variation changes the machine slightly:

[!INTERVIEW] Draw the machine first Sketch the states and arrows before you code. Each arrow becomes one term in a max. Interviewers find this far easier to follow than a recurrence that seems to come from nowhere, and it makes the k-transactions follow-up straightforward.

Other state-machine examples

House robber: two states, robbed this house or skipped it. House Robber II (houses in a circle) runs it twice: once without the first house, once without the last.
Maximum product subarray: track both the max and the min product ending here, because a negative number swaps them.
Domino and tromino tiling: states for "fully filled" and "one cell sticking out".
Paint houses or fences: the state is the color used last.

Interval DP

The state is dp[i][j] = the best answer for the range i..j. To compute it, try every split point k inside the range. Fill the table by increasing interval length. The cost is usually O(n³).

The key insight is often to think about the last operation, not the first. In *Burst Balloons*, choosing the first balloon to burst changes its neighbors in unpredictable ways. Choosing the last balloon k to burst in (i, j) fixes its neighbors as i and j, so the two sides become independent.

def max_coins(nums):
    a = [1] + nums + [1]
    n = len(a)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):                 # gap between the boundaries i and j
        for i in range(0, n - length):
            j = i + length
            dp[i][j] = max(dp[i][k] + a[i] * a[k] * a[j] + dp[k][j]
                           for k in range(i + 1, j))
    return dp[0][n - 1]

The same shape appears in:

Matrix chain multiplication: the cheapest place to split a product.
Minimum cost to cut a stick: sort the cuts, then decide which cut happens last within each segment.
Predict the winner / stone games: dp[i][j] = the best score difference the current player can get from the range i..j.
Palindrome partitioning and palindromic subsequences: see DP on Strings.

Recognizing which kind you have

[!TIP] Practice Stock with Cooldown · Stock with Transaction Fee · Best Time to Buy and Sell Stock III · Stock with k Transactions · House Robber II · Maximum Product Subarray · Burst Balloons · Matrix Chain Multiplication · Minimum Cost to Cut a Stick · Predict the Winner