Interval DP and Advanced Dynamic Programming: Burst Balloons, State Machine, Tree DP

By /

Interval DP and Advanced Dynamic Programming Patterns

Interval DP solves optimization problems over contiguous subarrays or subsequences. The core idea: the optimal solution for an interval [i, j] depends on solutions for smaller intervals within it. This guide covers interval DP and the other advanced DP patterns that appear in senior-level interviews.

Interval DP Template

Process all intervals of length 2, 3, …, n. For each interval [i, j], try all split points k and combine solutions for [i, k] and [k+1, j]:

n = len(arr)
dp = [[0] * n for _ in range(n)]

# Base case: intervals of length 1
for i in range(n):
    dp[i][i] = base_value(i)

# Fill for increasing lengths
for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = float('inf')  # or -inf for max problems
        for k in range(i, j):    # try all split points
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, k, j))

return dp[0][n-1]

Burst Balloons (LeetCode 312)

Pop all balloons to maximize coins. If you pop balloon k last in interval [i, j], it is surrounded by the boundary balloons (not yet popped):

def max_coins(nums):
    nums = [1] + nums + [1]   # add 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):  # k is the LAST balloon popped in [left, right]
                coins = nums[left] * nums[k] * nums[right]
                dp[left][right] = max(dp[left][right],
                                      dp[left][k] + coins + dp[k][right])
    return dp[0][n-1]
# Key insight: think "last balloon popped" not "first" — avoids tracking remaining balloons

Minimum Cost to Cut a Stick (LeetCode 1547)

def min_cost(n, cuts):
    cuts = [0] + sorted(cuts) + [n]
    m = len(cuts)
    dp = [[0] * m for _ in range(m)]

    for length in range(2, m):
        for i in range(m - length):
            j = i + length
            dp[i][j] = float('inf')
            for k in range(i + 1, j):
                dp[i][j] = min(dp[i][j],
                               dp[i][k] + dp[k][j] + cuts[j] - cuts[i])
    return dp[0][m-1]

Longest Palindromic Subsequence (LeetCode 516)

def longest_palindrome_subseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n): dp[i][i] = 1  # single char is palindrome

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

State Machine DP

Model problems where the state changes based on actions. Classic: Best Time to Buy and Sell Stock with Cooldown (LeetCode 309):

def max_profit(prices):
    # States: hold (own stock), sold (just sold, cooldown), rest (can buy)
    hold = float('-inf')   # max profit while holding
    sold = 0               # max profit day after selling (cooldown)
    rest = 0               # max profit while resting (can buy)

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

DP on Trees

# Diameter of Binary Tree (LeetCode 543):
def diameter_of_binary_tree(root):
    self.ans = 0
    def depth(node):
        if not node: return 0
        l = depth(node.left)
        r = depth(node.right)
        self.ans = max(self.ans, l + r)   # path through this node
        return max(l, r) + 1
    depth(root)
    return self.ans

# House Robber III — cannot rob adjacent nodes (LeetCode 337):
def rob(root):
    def dp(node):
        if not node: return 0, 0  # (rob_node, skip_node)
        l_rob, l_skip = dp(node.left)
        r_rob, r_skip = dp(node.right)
        rob_node = node.val + l_skip + r_skip
        skip_node = max(l_rob, l_skip) + max(r_rob, r_skip)
        return rob_node, skip_node
    return max(dp(root))

Digit DP

Count numbers in range [0, N] satisfying a digit-based constraint (e.g., no two consecutive equal digits):

def count_numbers(n):
    digits = list(str(n))
    from functools import lru_cache
    @lru_cache(None)
    def dp(pos, prev_digit, is_tight, started):
        if pos == len(digits): return 1 if started else 0
        limit = int(digits[pos]) if is_tight else 9
        result = 0
        for d in range(0, limit + 1):
            if started and d == prev_digit: continue  # constraint: no repeat
            result += dp(pos+1, d, is_tight and d==limit, started or d>0)
        return result
    return dp(0, -1, True, False)

Interval DP Problem List

Problem Key Insight LeetCode
Burst Balloons Last balloon popped 312
Minimum Cost to Cut Stick Cost = segment length 1547
Palindrome Partitioning II Min cuts = min intervals 132
Longest Palindromic Subsequence Expand/contract palindrome 516
Strange Printer Last char printed 664
Zuma Game Remove groups 488

Interview Tips

  • For interval DP: the outer loop must be on length, not on left boundary — always fill shorter intervals before longer ones
  • Burst Balloons: the “last popped” framing is the key insight — it avoids tracking which balloons remain
  • State machine DP: draw the state transitions explicitly before coding — hold/sold/rest or buy/sell/cooldown
  • Tree DP: the function returns a tuple (include_root, exclude_root) — this is the pattern for House Robber III, maximum sum BST, etc.
  • Digit DP: always use memoization with (position, prev_digit, is_tight, started) as state

  • Atlassian Interview Guide
  • Coinbase Interview Guide
  • Databricks Interview Guide
  • LinkedIn Interview Guide
  • Apple Interview Guide
  • Meta Interview Guide
    • Scroll to Top