loading

Burst Balloons — Step-by-Step Visualization

hardLeetCode #312ArrayDynamic Programming

You are given `n` balloons, indexed from `0` to `n - 1`. Each balloon is painted with a number on it, represented by an array `nums`. You are asked to burst all the balloons. If you burst the `i-th` balloon, you will get `nums[i - 1] * nums[i] * nums[i + 1]` coins. After the burst, the `i - 1` and `i + 1` then becomes adjacent. Find the maximum coins you can collect by bursting the balloons wisely.

Algorithm Pattern

Interval Dynamic Programming

Key Idea

Instead of thinking about which balloon to burst *first*, think about which balloon is burst *last* in a given range `[i, j]`. If the $k$-th balloon is burst last in `[i, j]`, the coins gained are `nums[i-1] * nums[k] * nums[j+1] + dp[i][k-1] + dp[k+1][j]`. We use a 2D DP table where `dp[i][j]` stores the maximum coins for the range from index `i` to `j`.

Step-by-Step Approach

  1. Add virtual balloons with value `1` at both ends of the array.
  2. Initialize a 2D DP table of size $(n+2) imes (n+2)$.
  3. Iterate through all possible interval lengths from 1 to $n$.
  4. For each length, iterate through all possible starting positions `i`.
  5. Calculate the end of the interval `j = i + length - 1`.
  6. Iterate through each balloon `k` in the interval `[i, j]` as the 'last to burst'.
  7. Update `dp[i][j] = max(dp[i][j], new_coins)`.

Common Gotchas

  • The order of loops (length, then start, then $k$) is critical for DP dependency.
  • Virtual boundaries (index 0 and $n+1$) are essential for edge calculations.

Related Problems

← All problems