Burst Balloons

hard array dp

Problem

Each balloon has a value. Bursting balloon i earns nums[left] · nums[i] · nums[right] coins, where left/right are the neighbours still standing. Return the maximum coins obtainable by bursting all balloons.

Inputnums = [3, 1, 5, 8]

Output167

nums

def max_coins(nums):
    a = [1] + nums + [1]
    n = len(a)
    dp = [[0]*n for _ in range(n)]
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            for k in range(i + 1, j):
                dp[i][j] = max(dp[i][j], dp[i][k] + a[i]*a[k]*a[j] + dp[k][j])
    return dp[0][n - 1]

function maxCoins(nums) {
  const a = [1, ...nums, 1];
  const n = a.length;
  const dp = Array.from({ length: n }, () => new 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] + a[i] * a[k] * a[j] + dp[k][j]);
      }
    }
  }
  return dp[0][n - 1];
}

class Solution {
    public int maxCoins(int[] nums) {
        int m = nums.length;
        int n = m + 2;
        int[] a = new int[n];
        a[0] = a[n-1] = 1;
        for (int i = 0; i < m; i++) a[i+1] = nums[i];
        int[][] dp = new int[n][n];
        for (int len = 2; len < n; len++)
            for (int i = 0; i + len < n; i++) {
                int j = i + len;
                for (int k = i + 1; k < j; k++)
                    dp[i][j] = Math.max(dp[i][j], dp[i][k] + a[i]*a[k]*a[j] + dp[k][j]);
            }
        return dp[0][n - 1];
    }
}

int maxCoins(vector<int>& nums) {
    int m = nums.size(), n = m + 2;
    vector<int> a(n, 1);
    for (int i = 0; i < m; i++) a[i + 1] = nums[i];
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 2; len < n; len++)
        for (int i = 0; i + len < n; i++) {
            int j = i + len;
            for (int k = i + 1; k < j; k++)
                dp[i][j] = max(dp[i][j], dp[i][k] + a[i]*a[k]*a[j] + dp[k][j]);
        }
    return dp[0][n - 1];
}

Explanation

The clever trick here is to think backwards. Instead of asking "which balloon do I pop first?", we ask "which balloon is the last one popped in a given range?". That single change makes the problem easy to break into independent pieces.

First we pad the array with a 1 on each side, so a = [1] + nums + [1]. These sentinels act as the permanent neighbours that never get popped, which avoids messy edge cases at the borders.

We fill a table dp[i][j] = the most coins you can earn by bursting every balloon strictly between positions i and j. If balloon k is the last one popped in that range, its neighbours are exactly i and j (everything else between them is already gone), so it earns a[i]*a[k]*a[j], plus the best from the left sub-range dp[i][k] and the right sub-range dp[k][j].

We try every possible k and keep the maximum. Because shorter ranges are solved before longer ones, the sub-answers are always ready when we need them.

Example: nums = [3, 1, 5, 8] becomes [1, 3, 1, 5, 8, 1]. The table builds up range by range and the final answer sits in dp[0][n-1], which works out to 167.

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