Burst Balloons Hard 0 attempts
LeetCode ↗

Burst Balloons

Hard Dynamic ProgrammingMemoization LeetCode

You're given n balloons lined up in a row, each labeled with a number in the array nums. Bursting balloon i earns nums[i-1] * nums[i] * nums[i+1] coins, where the two neighbors are whatever balloons currently remain adjacent to it (treat positions just past either end as holding an implicit 1). Burst all the balloons, choosing the order that maximizes total coins collected, and return that maximum.

Input Format
Implement maxCoins(nums). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
nums = [3,1,5,8]
Output
167

Example 2

Input
nums = [1,5]
Output
10
Constraints
  • 1 <= nums.length <= 300
  • 0 <= nums[i] <= 100
Test Cases (2)
Case 1
Args: [[3,1,5,8]] Expected: 167
Case 2
Args: [[1,5]] Expected: 10
Topics
Dynamic ProgrammingMemoization

Interval DP

dp[i][j] = max coins from bursting all balloons between i and j.

javascript
function maxCoins(nums) {
  const a = [1, ...nums, 1], n = a.length;
  const dp = Array.from({length: n}, () => Array(n).fill(0));
  for (let len = 2; len < n; len++) {
    for (let i = 0; i + len < n; i++) {
      const j = i + len;
      for (let k = i + 1; k < j; k++) {
        dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + a[i]*a[k]*a[j]);
      }
    }
  }
  return dp[0][n-1];
}

Time: O(n³) | Space: O(n²)

Saved in this browser only. Private to you.

JavaScript