Advanced

Interval & Game DP

Interval DP problems operate on ranges [i, j] where you try every possible split point. Game DP problems model two-player games where both players play optimally. These are among the hardest DP patterns but follow a consistent template.

Problem 1: Burst Balloons

Problem: Given n balloons with numbers on them, burst them one by one. When you burst balloon i, you earn nums[left] * nums[i] * nums[right] coins, where left and right are the adjacent surviving balloons. Find the maximum coins you can collect.

Key insight: Instead of thinking about which balloon to burst first (which changes the neighbors), think about which balloon to burst last in each interval. The last balloon burst in interval [i, j] has fixed neighbors: nums[i-1] and nums[j+1].

State: dp[i][j] = maximum coins from bursting all balloons between i and j (exclusive).

# Brute force: O(n! * n) - try every permutation of burst order
# (impractical, shown conceptually)

# Memoization: O(n^3) time, O(n^2) space
def burst_balloons_memo(nums):
    nums = [1] + nums + [1]  # Add boundary balloons
    n = len(nums)
    memo = {}
    def dp(left, right):
        if left + 1 == right:  # No balloons between left and right
            return 0
        if (left, right) in memo:
            return memo[(left, right)]
        result = 0
        for k in range(left + 1, right):
            # k is the LAST balloon to burst in (left, right)
            coins = nums[left] * nums[k] * nums[right]
            result = max(result, dp(left, k) + coins + dp(k, right))
        memo[(left, right)] = result
        return result
    return dp(0, n - 1)

# Tabulation: O(n^3) time, O(n^2) space
def burst_balloons_tab(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    # Fill by interval length
    for length in range(2, n):  # length of interval (exclusive endpoints)
        for left in range(0, n - length):
            right = left + length
            for k in range(left + 1, 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]

# Test: burst_balloons_tab([3, 1, 5, 8]) = 167
# Optimal order: burst 1, then 5, then 3, then 8
# 3*1*5=15, 3*5*8=120, 1*3*8=24, 1*8*1=8 -> 167

Problem 2: Stone Game

Problem: Two players take turns picking stones from either end of a row. Each player plays optimally to maximize their own score. Determine the maximum score the first player can guarantee.

State: dp[i][j] = maximum score advantage (player's score minus opponent's score) the current player can achieve from stones[i..j].

# Memoization: O(n^2) time
def stone_game_memo(piles):
    memo = {}
    def dp(i, j):
        if i > j:
            return 0
        if (i, j) in memo:
            return memo[(i, j)]
        # Current player picks left or right
        # After picking, it's opponent's turn, so subtract their optimal score
        pick_left = piles[i] - dp(i + 1, j)
        pick_right = piles[j] - dp(i, j - 1)
        memo[(i, j)] = max(pick_left, pick_right)
        return memo[(i, j)]
    score_diff = dp(0, len(piles) - 1)
    total = sum(piles)
    # Player 1's score = (total + score_diff) / 2
    return (total + score_diff) // 2

# Tabulation: O(n^2) time, O(n^2) space
def stone_game_tab(piles):
    n = len(piles)
    # dp[i][j] = score advantage for current player from piles[i..j]
    dp = [[0] * n for _ in range(n)]

    # Base case: single pile, current player takes it
    for i in range(n):
        dp[i][i] = piles[i]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(piles[i] - dp[i+1][j],
                          piles[j] - dp[i][j-1])

    score_diff = dp[0][n - 1]
    total = sum(piles)
    return (total + score_diff) // 2

# Test: stone_game_tab([5, 3, 4, 5]) = 10
# Player 1 picks 5, Player 2 picks 5, Player 1 picks 4, Player 2 picks 3
# Player 1 score: 5 + 4 = 9... but optimal is 5 + 5 = 10

Problem 3: Minimum Cost Tree From Leaf Values

Problem: Given an array of positive integers (leaf values in in-order), build a binary tree where each non-leaf node's value is the product of the maximum leaf values in its left and right subtrees. Minimize the sum of all non-leaf node values.

State: dp[i][j] = minimum sum of non-leaf nodes for the subtree covering leaves i..j.

# Memoization: O(n^3) time, O(n^2) space
def mct_from_leaf(arr):
    n = len(arr)
    # Precompute max values for all ranges
    max_val = [[0] * n for _ in range(n)]
    for i in range(n):
        max_val[i][i] = arr[i]
        for j in range(i + 1, n):
            max_val[i][j] = max(max_val[i][j-1], arr[j])

    memo = {}
    def dp(i, j):
        if i == j:
            return 0  # Single leaf, no non-leaf node cost
        if (i, j) in memo:
            return memo[(i, j)]
        result = float('inf')
        for k in range(i, j):
            # Split: left subtree = [i..k], right subtree = [k+1..j]
            cost = (max_val[i][k] * max_val[k+1][j] +
                    dp(i, k) + dp(k+1, j))
            result = min(result, cost)
        memo[(i, j)] = result
        return result
    return dp(0, n - 1)

# Greedy O(n) solution using monotonic stack
def mct_from_leaf_greedy(arr):
    # Use a monotonic decreasing stack
    stack = [float('inf')]
    result = 0
    for val in arr:
        while stack[-1] <= val:
            mid = stack.pop()
            result += mid * min(stack[-1], val)
        stack.append(val)
    while len(stack) > 2:
        result += stack.pop() * stack[-1]
    return result

# Test: mct_from_leaf([6, 2, 4]) = 32
# Tree: root=24 (6*4), left=6, right_node=8 (2*4), right_left=2, right_right=4
# Sum of non-leaf nodes: 24 + 8 = 32

Problem 4: Palindrome Partitioning II (Minimum Cuts)

Problem: Given a string s, find the minimum number of cuts needed to partition s such that every substring in the partition is a palindrome.

# Brute force: O(2^n * n) - try every partition
def min_cut_brute(s):
    n = len(s)
    def is_pal(i, j):
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

    def dp(start):
        if start == n:
            return -1  # No cut needed after the string ends
        result = float('inf')
        for end in range(start, n):
            if is_pal(start, end):
                result = min(result, 1 + dp(end + 1))
        return result
    return dp(0)

# Optimized DP: O(n^2) time, O(n^2) space
def min_cut_dp(s):
    n = len(s)

    # Precompute palindrome table
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or is_pal[i+1][j-1]):
                is_pal[i][j] = True

    # dp[i] = minimum cuts to partition s[0..i]
    dp = list(range(n))  # Worst case: cut after every character
    for i in range(1, n):
        if is_pal[0][i]:
            dp[i] = 0
            continue
        for j in range(1, i + 1):
            if is_pal[j][i]:
                dp[i] = min(dp[i], dp[j-1] + 1)
    return dp[n - 1]

# Test: min_cut_dp("aab") = 1 ("aa" | "b")
# Test: min_cut_dp("a") = 0
# Test: min_cut_dp("ab") = 1

Problem 5: Optimal Binary Search Tree

Problem: Given sorted keys with search frequencies, construct a BST that minimizes the total search cost (sum of frequency * depth for each key).

State: dp[i][j] = minimum search cost for a BST containing keys i through j.

# Tabulation: O(n^3) time, O(n^2) space
def optimal_bst(keys, freq):
    n = len(keys)
    # dp[i][j] = minimum cost BST for keys[i..j]
    dp = [[0] * n for _ in range(n)]
    # prefix_freq[i][j] = sum of frequencies from i to j
    prefix_freq = [[0] * n for _ in range(n)]

    for i in range(n):
        prefix_freq[i][i] = freq[i]
        dp[i][i] = freq[i]  # Single key: cost = its frequency * depth 1
        for j in range(i + 1, n):
            prefix_freq[i][j] = prefix_freq[i][j-1] + freq[j]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            total_freq = prefix_freq[i][j]

            for k in range(i, j + 1):
                # k is the root of this subtree
                left_cost = dp[i][k-1] if k > i else 0
                right_cost = dp[k+1][j] if k < j else 0
                # When k becomes root, all other nodes go one level deeper
                # so their costs increase by their frequencies
                cost = left_cost + right_cost + total_freq
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]

# Test: optimal_bst([10, 12, 20], [34, 8, 50]) = 142
# Optimal: 20 as root, 10 as left child, 12 as left-right grandchild
# Cost: 50*1 + 34*2 + 8*3 = 50 + 68 + 24 = 142

Complexity Summary

Problem	Brute Force	DP Time	DP Space
Burst Balloons	O(n!)	O(n^3)	O(n^2)
Stone Game	O(2^n)	O(n^2)	O(n^2)
Min Cost Tree	O(Catalan(n))	O(n^3)	O(n^2)
Palindrome Partitioning	O(2^n × n)	O(n^2)	O(n^2)
Optimal BST	O(Catalan(n))	O(n^3)	O(n^2)

Key Takeaways

• Interval DP always uses dp[i][j] for a range and tries every split point k. Fill order is by increasing interval length.
• The "last operation" trick (burst balloons) converts a dependent subproblem structure into independent subproblems.
• Game DP uses the minimax principle: your gain is the opponent's loss. The recurrence subtracts the opponent's optimal play.
• All five problems are O(n^2) or O(n^3) and cannot be space-optimized below O(n^2) because dp[i][j] depends on non-adjacent entries.
• Some interval DP problems have greedy O(n) solutions (min cost tree with monotonic stack), but the DP approach is more general and easier to derive in interviews.