Burst Balloons Hard 0 attempts
LeetCode ↗

Burst Balloons

Hard Dynamic ProgrammingMemoization LeetCode

Given n balloons with numbers on them, burst them to maximize coins. When you burst balloon i, you get nums[i-1] * nums[i] * nums[i+1] coins.

Example: nums = [3,1,5,8] → Output: 167

Sample Input
—
Sample Output
—
Constraints
  • 1 <= nums.length <= 300
  • 0 <= nums[i] <= 100
Test Cases
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.

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