Tiling and Interval Partitioning: Recursion to DP

Problem Statement#

This post covers the genre where pure backtracking is too slow but the recursion structure points the way to interval DP. Three canonical examples:

• Domino Tiling of a 2 by n board: how many ways to tile? Returns the Fibonacci numbers.
• Burst Balloons (LeetCode 312): burst balloons one by one to maximize nums[left] * nums[i] * nums[right] coins, where left and right are the current neighbors after previous bursts.
• Minimum Cost to Cut a Stick (LeetCode 1547): cut a stick of length n at given cut positions; the cost of each cut equals the current segment length. Minimize total cost.

These problems share a partition recursion: pick the last operation to perform on an interval, recurse on the two halves, combine with a constant-time merge.

Why This Problem Matters#

Burst Balloons is a hard-tier interview at Amazon, Google, and Meta. The reason is the counterintuitive recursion: thinking "which balloon do I burst FIRST" leads nowhere because the neighbors keep changing. Flipping to "which balloon do I burst LAST in this interval" decouples the subproblems — once we fix the last burst, the left and right intervals never again interfere with each other. Candidates who can make that mental flip on the spot are extremely rare and earn senior-level signal.

LC 1547 (Minimum Cost to Cut a Stick) follows the same template, and many tiling problems decompose with similar recursion. Mastering this pattern unlocks the entire interval-DP family: matrix-chain multiplication, optimal BST, Different Ways to Add Parentheses, and Burst Balloons itself.

The Core Insight (decision tree / state space)#

For Burst Balloons, augment the array with virtual 1s on both ends: nums = [1] + nums + [1]. State is (left, right) — the interval of balloons strictly between indices left and right that have not yet burst. Decision: which balloon k in (left, right) is the LAST to burst?

When balloon k bursts last, all balloons in (left, k) have already burst (so k's left neighbor at burst time is left) and all balloons in (k, right) have already burst (so k's right neighbor is right). The recurrence is:

dp[left][right] = max over k in (left, right) of
                  dp[left][k] + dp[k][right] + nums[left] * nums[k] * nums[right]

The state space is O(n^2) and each state does O(n) work, giving O(n^3) overall — a polynomial replacement for the exponential brute force.

For LC 1547, the same flip works: among the cuts available in the interval (i, j), decide which cut to make LAST. The cost of that cut is cuts[j] - cuts[i] plus the optimal subdivisions of the left and right intervals.

Visual Dry Run (recursion tree)#

For nums = [3, 1, 5, 8], augmented to [1, 3, 1, 5, 8, 1]:

solve(0, 5)  // interval (1,3,1,5,8)
  k=1 (val 3): coins = 1*3*1 + solve(0,1) + solve(1,5)
  k=2 (val 1): coins = 1*1*1 + solve(0,2) + solve(2,5)
  k=3 (val 5): coins = 1*5*1 + solve(0,3) + solve(3,5)
  k=4 (val 8): coins = 1*8*1 + solve(0,4) + solve(4,5)
  return max

Each subcall has the same shape and is memoized. The DP table fills up bottom-up by interval length, ensuring smaller intervals are solved before larger ones.

Solution (Optimal) — Python + JavaScript with backtracking template, complexity#

Burst Balloons (LeetCode 312):

def maxCoins(nums):
    nums = [1] + nums + [1]
    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
            best = 0
            for k in range(left + 1, right):
                coins = nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right]
                if coins > best:
                    best = coins
            dp[left][right] = best
    return dp[0][n - 1]

function maxCoins(nums) {
  const arr = [1, ...nums, 1];
  const n = arr.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(0));
  for (let length = 2; length < n; length++) {
    for (let left = 0; left < n - length; left++) {
      const right = left + length;
      let best = 0;
      for (let k = left + 1; k < right; k++) {
        const coins = arr[left] * arr[k] * arr[right] + dp[left][k] + dp[k][right];
        if (coins > best) best = coins;
      }
      dp[left][right] = best;
    }
  }
  return dp[0][n - 1];
}

Minimum Cost to Cut a Stick (LeetCode 1547):

def minCost(n, cuts):
    cuts = sorted([0] + 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
            best = float('inf')
            for k in range(i + 1, j):
                cost = dp[i][k] + dp[k][j] + cuts[j] - cuts[i]
                if cost < best:
                    best = cost
            dp[i][j] = best
    return dp[0][m - 1]

Complexity: O(n^3) time, O(n^2) space for both. Domino tiling is O(n) via Fibonacci.

Common Mistakes#

• Trying "which balloon to burst FIRST." This couples the subproblems and forces exponential time.
• Forgetting to pad with 1s on both ends — the boundary multiplications go wrong.
• Iterating intervals top-down without memoization — degenerates to exponential.
• Confusing dp[i][k] and dp[k][j] boundaries; remember intervals are half-open or fully open as defined.

Interview Tips#

• Lead with the "burst last" flip. Saying "I'll define dp[l][r] as the max coins from bursting all balloons strictly between l and r, picking k as the last burst" is gold.
• Mention the O(n^3) bound and explain why the cubic is unavoidable for general interval DP.
• Sketch the augmentation with virtual 1s — interviewers love this concrete step.
• Reference LC 1547, LC 1000 (Min Cost to Merge Stones), and LC 241 (Different Ways to Add Parentheses) as the same family.

Follow-up Questions#

• Different Ways to Add Parentheses (LC 241): same partition recursion, divide-and-conquer flavor.
• Min Cost to Merge Stones (LC 1000): interval DP with merge constraint.
• Strange Printer (LC 664): interval DP for layered printing.
• Optimal BST and matrix-chain multiplication — classic textbook interval DP.

Key Takeaways#

• The pattern: when a problem mutates the array as you operate on it, flip from "which one first" to "which one last."
• Burst Balloons LC 312 is the textbook example; pad with 1s and define dp[l][r].
• All interval-DP problems share the same shape: outer loop over length, inner loops over left and split point.
• O(n^3) time and O(n^2) space are typical and acceptable for n up to a few hundred.
• This pattern unlocks LC 1547, LC 1000, LC 664, and LC 241 — the entire interval DP family.
• A FAANG hard-tier interview separator: candidates who flip the recursion stand out instantly.

Sources:

• 312. Burst Balloons - In-Depth Explanation
• Burst Balloons | Partition DP | DP 51 - takeuforward