Blind Plus 100 Visualized

#94 · 2D DP

Burst Balloons

You are given n balloons with numbers nums[i]. Bursting balloon i earns nums[i - 1] * nums[i] * nums[i + 1] coins (out-of-range neighbours count as 1). Return the maximum coins you can collect by bursting all balloons wisely.

HardLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Interval DP table

dp[l][r] is the best score from bursting every balloon strictly between positions l and r, assuming l and r stay in place as walls. The recurrence picks the LAST balloon k to burst in (l, r): its neighbours are exactly p[l] and p[r], so dp[l][r] = max over k of dp[l][k] + p[l]·p[k]·p[r] + dp[k][r].

Memory layout

A (n + 2) × (n + 2) array, only the upper triangle is used. Flatten to one array for locality.

OperationCost
timeO(n³)
spaceO(n²)

Padded array with sentinel 1s

Prepending and appending a 1 removes all boundary special cases: every real balloon has two neighbours, and the outer walls are never burst.

Memory layout

One extra element at each end.

OperationCost
overheadO(1) extra

Why it fits

  • Choosing the FIRST balloon to burst creates dependencies (neighbours change), but choosing the LAST balloon in a range makes the two sub-ranges independent, which is the structure DP needs.
  • There are only O(n²) distinct ranges and each is solved by trying O(n) last balloons, giving O(n³) instead of n! orderings.
  • Filling the table by increasing range length guarantees both sub-ranges of any range are ready.

Why alternatives degrade

Greedy (burst the smallest first):
Locally cheap bursts can destroy large products later; counterexamples are easy to build.
Trying all n! orders:
Exponential; even n = 15 is too large.
DP on "first balloon burst":
After a burst the remaining balloons are no longer contiguous in a way that splits into independent halves.

Four approaches, from naive to production

1 · beginner

Plain recursion on the last balloon

time O(3ⁿ)space O(n)

For a range between walls l and r, try each balloon k as the last one to burst: it scores p[l]·p[k]·p[r] plus the best of the two sides. Recurse without remembering results.

int maxCoins(vector<int>& nums) {
    vector<int> p{1}; p.insert(p.end(), nums.begin(), nums.end()); p.push_back(1);
    function<int(int, int)> solve = [&](int l, int r) -> int {
        int best = 0;
        for (int k = l + 1; k < r; k++) {
            int coins = p[l] * p[k] * p[r] + solve(l, k) + solve(k, r);
            best = max(best, coins);
        }
        return best;
    };
    return solve(0, (int)p.size() - 1);
}

Flaws & bottlenecks

  • The same (l, r) pair is solved again and again.
  • Roughly three-way branching: exponential time.
  • Recursion depth up to n.

Interviewer cross-questions

Why consider the last balloon instead of the first?

Say: When the last balloon k is burst, its neighbours are the walls l and r, which are fixed; the left and right parts are independent subproblems.

What is the base case?

Say: Two adjacent walls enclose no balloon, so the score is 0.

How do you fix the repeated work?

Say: Cache solve(l, r) in a table.

2 · intermediate

Memoised recursion

time O(n³)space O(n²)

Same recursion with a table memo[l][r] consulted before computing, so each of the O(n²) ranges is solved once.

int maxCoins(vector<int>& nums) {
    vector<int> p{1}; p.insert(p.end(), nums.begin(), nums.end()); p.push_back(1);
    vector<vector<int>> memo(p.size(), vector<int>(p.size(), -1));
    function<int(int, int)> solve = [&](int l, int r) -> int {
        if (r - l < 2) return 0;
        if (memo[l][r] != -1) return memo[l][r];
        int best = 0;
        for (int k = l + 1; k < r; k++) {
            int coins = p[l] * p[k] * p[r] + solve(l, k) + solve(k, r);
            best = max(best, coins);
        }
        memo[l][r] = best;
        return best;
    };
    return solve(0, (int)p.size() - 1);
}

Flaws & bottlenecks

  • Recursion depth up to n.
  • Function call overhead for every state.
  • Still O(n²) memory.

Interviewer cross-questions

Why O(n³)?

Say: There are O(n²) ranges and each tries up to n values of k.

Which cells are needed?

Say: All ranges (l, r) with r − l ≥ 2 reachable from the full range; here every one of them.

How to avoid recursion?

Say: Iterate over range length, from short to long.

3 · advanced

Bottom-up by range length

time O(n³)space O(n²)

Loop gap = 2…n+1 (the distance between walls), loop l, and take the maximum over k of dp[l][k] + p[l]·p[k]·p[r] + dp[k][r].

int maxCoins(vector<int>& nums) {
    vector<int> p{1}; p.insert(p.end(), nums.begin(), nums.end()); p.push_back(1);
    int n = p.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int gap = 2; gap < n; gap++) {
        for (int l = 0; l + gap < n; l++) {
            int r = l + gap;
            for (int k = l + 1; k < r; k++) {
                dp[l][r] = max(dp[l][r], dp[l][k] + p[l] * p[k] * p[r] + dp[k][r]);
            }
        }
    }
    return dp[0][n - 1];
}

Flaws & bottlenecks

  • Three nested loops; 500 balloons is about 2 × 10⁷ steps per ... fine, but 5000 would not be.
  • Uses a 2D array of arrays (pointer chasing).
  • Recomputes p[l] · p[r] inside the k loop.

Interviewer cross-questions

Why does the order guarantee dp[l][k] and dp[k][r] are ready?

Say: Both have a smaller gap than (l, r), and all smaller gaps were completed in earlier iterations of the outer loop.

Can the complexity be lower?

Say: O(n³) is the standard bound; no widely used faster exact method exists for this problem.

How do you recover the burst order?

Say: Store the best k for every (l, r) and expand recursively: k is last in (l, r); then handle (l, k) and (k, r).

4 · expert

Flat table, hoisted product, zeros removed

time O(n³)space O(n²)

Drop zero-valued balloons (burst them first for free), pad with 1s, and store dp in one flat array. Iterate l downward and r upward, hoisting p[l]·p[r] out of the k loop.

int maxCoins(vector<int>& nums) {
    vector<int> vals;
    for (int v : nums) if (v > 0) vals.push_back(v);
    int n = vals.size();
    if (n == 0) return 0;
    vector<long long> p(n + 2);
    p[0] = p[n + 1] = 1;
    for (int i = 0; i < n; i++) p[i + 1] = vals[i];
    int w = n + 2;
    vector<long long> dp((size_t)w * w, 0);
    for (int l = n - 1; l >= 0; l--) {
        for (int r = l + 2; r < w; r++) {
            long long best = 0;
            long long base = p[l] * p[r];
            for (int k = l + 1; k < r; k++) {
                long long v = dp[(size_t)l * w + k] + base * p[k] + dp[(size_t)k * w + r];
                if (v > best) best = v;
            }
            dp[(size_t)l * w + r] = best;
        }
    }
    return (int)dp[w - 1];
}

Flaws & bottlenecks

  • Same asymptotic cost; gains are constant-factor and from removing zeros.
  • Index arithmetic (l · w + k) is error prone.
  • The zero-removal argument needs a short proof.

Interviewer cross-questions

Why can zeros be removed?

Say: A zero scores nothing and only turns the product of any neighbour burst while it is adjacent into 0. Bursting zeros first removes that harm at no cost, so some optimal order does so.

Why a flat array?

Say: Contiguous memory is cache friendly and avoids an array-of-arrays indirection; the inner loop over k reads dp[l*w+k] sequentially.

What about overflow?

Say: Values up to 100 with 500 balloons already exceed 10⁹ in intermediate sums for adversarial inputs; use 64-bit integers if the limits grow.

Synchronized code walkthrough

Showing: Plain recursion on the last balloon — shares the player above; click any step to jump.

int maxCoins(vector<int>& nums) {
    vector<int> p{1}; p.insert(p.end(), nums.begin(), nums.end()); p.push_back(1);
    function<int(int, int)> solve = [&](int l, int r) -> int {
        int best = 0;
        for (int k = l + 1; k < r; k++) {
            int coins = p[l] * p[k] * p[r] + solve(l, k) + solve(k, r);
            best = max(best, coins);
        }
        return best;
    };
    return solve(0, (int)p.size() - 1);
}