Advanced Dynamic Programming Patterns: State Machine, Interval DP, Tree DP, Bitmask

By /

Advanced Dynamic Programming Patterns

Beyond the foundational DP patterns (Fibonacci, 0/1 knapsack, LCS), advanced interviews test state machine DP, interval DP, tree DP, and multi-dimensional DP. Each pattern has a distinct structure for defining states and transitions. Recognizing the pattern from the problem description is the critical skill.

  • Databricks Interview Guide
  • Atlassian Interview Guide
  • Uber Interview Guide
  • LinkedIn Interview Guide
  • Apple Interview Guide
  • Meta Interview Guide

    • Pattern 1: State Machine DP

    Problems where you’re in one of several states and transitions between states have costs or values. Define dp[i][state] = best outcome at position i in the given state.

    Best Time to Buy and Sell Stock with Cooldown

    States: holding stock, sold stock (cooldown active), rest (no stock, no cooldown).

    def max_profit(prices):
    held = -float('inf')  # max profit while holding
    sold = 0              # max profit day after selling (cooldown)
    rest = 0              # max profit while resting

    for price in prices:
        prev_held, prev_sold, prev_rest = held, sold, rest
        held = max(prev_held, prev_rest - price)  # keep holding or buy
        sold = prev_held + price                   # sell today
        rest = max(prev_rest, prev_sold)           # rest or come off cooldown
    return max(sold, rest)

    The key: identify all states, define transitions between them. Other state machine problems: stock with transaction fee, stock with K transactions.

    Pattern 2: Interval DP

    Problems where you process intervals [i, j] and the optimal solution depends on how you split the interval. Define dp[i][j] = optimal value for the subproblem on range [i, j].

    Burst Balloons

    Bursting balloon k in range [i, j] contributes nums[i-1] * nums[k] * nums[j+1]. The key insight: think of k as the LAST balloon burst in [i, j], not the first. This avoids dependencies on already-burst balloons.

    def max_coins(nums):
    nums = [1] + nums + [1]  # boundary sentinels
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for k in range(left + 1, right):
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][k] + nums[left]*nums[k]*nums[right] + dp[k][right]
                )
    return dp[0][n-1]

    Matrix Chain Multiplication / Minimum Cost to Merge Stones

    Same pattern: split interval at position k, compute cost of both halves plus cost of combining them. Fill DP table by increasing interval length.

    Pattern 3: Tree DP

    DP on trees where the answer at a node depends on its children. Define dp[node] = some optimal value for the subtree rooted at node. Process with post-order DFS (process children before parent).

    House Robber III (Binary Tree)

    Rob a binary tree where you cannot rob a parent and child. For each node, return a tuple: (rob_this_node, skip_this_node). rob = node.val + skip_left + skip_right. skip = max(rob_left, skip_left) + max(rob_right, skip_right).

    Diameter of Binary Tree

    Track global max diameter while computing subtree heights. dp[node] = height of subtree. At each node: diameter through this node = left_height + right_height. Update global max.

    Binary Tree Maximum Path Sum

    dp[node] = max sum of a path starting at this node going downward (can only extend one child). At each node: update global max with left_gain + node.val + right_gain (a path can go through both children but then cannot extend upward).

    Pattern 4: Digit DP

    Count numbers in range [0, N] satisfying a property (e.g., “no two consecutive same digits”). State: current position, whether we’re still bounded by N’s digits (tight constraint), any accumulated state.

    # Count integers in [1, n] where digits don't repeat
def count_no_repeat(n):
    digits = list(map(int, str(n)))

    @lru_cache(maxsize=None)
    def dp(pos, tight, used_mask):
        if pos == len(digits):
            return 1  # valid number
        limit = digits[pos] if tight else 9
        count = 0
        for d in range(0 if pos > 0 else 1, limit + 1):
            if used_mask & (1 << d):
                continue  # digit already used
            count += dp(pos+1, tight and d==limit, used_mask | (1<<d))
        return count

    return dp(0, True, 0)

    Pattern 5: Bitmask DP

    Problems with small N (usually N ≤ 20) where state includes which subset of items has been used. State: dp[mask] = optimal value having processed items in the bitmask.

    Traveling Salesman Problem (TSP)

    dp[mask][node] = shortest path visiting exactly the nodes in mask, ending at node
dp[mask | (1 << next)][next] = min(dp[mask][node] + dist[node][next])
Answer: min(dp[full_mask][last] + dist[last][start]) over all last nodes

    Minimum Cost to Connect All Points / Assign Workers

    Any problem about “assign N items to N positions with minimum cost” where N ≤ 20 fits bitmask DP. 2^N states × N positions = 2^20 × 20 ≈ 20M states for N=20. Feasible.

    Recognizing the Pattern

    • State machine: problem has discrete “modes” with different rules per mode
    • Interval DP: problem involves splitting a sequence/range optimally
    • Tree DP: problem is defined on a tree with constraints on parent-child relationships
    • Digit DP: count numbers in range satisfying constraints on their digits
    • Bitmask DP: assignment problems with N ≤ 20 items

    Interview Tips

    • For interval DP: always clarify what “splitting at k” means in your problem — is k the last item processed? The split point? Get this right first.
    • For tree DP: define what dp[node] returns very precisely before coding. Often it needs to return a tuple (with/without including root) to handle parent constraints.
    • State machine DP: draw the state transition diagram on the whiteboard first. Coding is mechanical once the diagram is clear.
    • Bitmask DP: the O(2^N * N) complexity — confirm N is small enough before proposing this approach.

    {
    “@context”: “https://schema.org”,
    “@type”: “FAQPage”,
    “mainEntity”: [
    {
    “@type”: “Question”,
    “name”: “How do you solve stock trading problems using state machine DP?”,
    “acceptedAnswer”: { “@type”: “Answer”, “text”: “Stock trading problems are state machine DP: define discrete states (holding, sold/cooldown, rest/idle) and transitions between them. For Stock with Cooldown: held = max profit while holding a stock; sold = max profit on the day after selling (cooldown day); rest = max profit while not holding and not in cooldown. Transitions: held = max(prev_held, prev_rest – price) [keep holding or buy from rest state]; sold = prev_held + price [sell today]; rest = max(prev_rest, prev_sold) [stay resting or come off cooldown]. Process each price, update all three states simultaneously using previous values. Answer: max(sold, rest). For K transactions: extend state to dp[k][holding] = max profit with at most k transactions used, currently holding or not.” }
    },
    {
    “@type”: “Question”,
    “name”: “What is interval DP and how do you identify when to use it?”,
    “acceptedAnswer”: { “@type”: “Answer”, “text”: “Interval DP applies when you process a sequence by splitting it into subintervals and the optimal solution for [i, j] depends on optimal solutions for smaller intervals. Key identifiers: (1) the problem involves merging, splitting, or processing a sequence where order matters, (2) the cost of combining two subresults depends on how you split them, (3) small N (typically ≤ 500) since interval DP is O(N^3). Classic problems: Burst Balloons (last balloon k to burst in range [i,j]), Matrix Chain Multiplication (minimize multiplication cost), Minimum Cost to Merge Stones (merge adjacent stones in groups of K). The critical trick for Burst Balloons: think of k as the LAST balloon burst, not the first — this avoids dependencies on already-burst elements that would complicate the recurrence. Fill the DP table by increasing interval length, always from smaller subproblems to larger ones.” }
    },
    {
    “@type”: “Question”,
    “name”: “How does bitmask DP solve assignment problems?”,
    “acceptedAnswer”: { “@type”: “Answer”, “text”: “Bitmask DP uses an integer where each bit represents whether an item has been used. dp[mask] = optimal cost when exactly the items in mask have been assigned. For N workers and N tasks: dp[mask] = minimum cost to assign tasks to the first popcount(mask) workers, where bit i is set if task i is assigned. Transition: for each unassigned task j (bit j not set in mask), dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cost[worker_index][j]). Worker index = popcount(mask) (we always assign the next worker). Time: O(2^N * N), Space: O(2^N). For N=20: ~20M states — feasible. For TSP with N=20 cities: dp[mask][last_city] = shortest path visiting exactly cities in mask and ending at last_city. This is O(2^N * N^2). Recognize bitmask DP when: N ≤ 20, all subsets matter, and "which items have been used" defines the state.” }
    }
    ]
    }

    Scroll to Top