Intuition
Instead of deciding which balloon to burst first, decide which one is burst LAST in each open interval. When k is last, its neighbours are the fixed interval boundaries, so the two sub-intervals become independent.
Explanation
Think 'last', not 'first'
Bursting first is hard because a balloon's neighbours keep changing. Flip it: in an open interval (left, right), pick the balloon k that is burst last. At that moment its only remaining neighbours are left and right (all interior balloons already gone), so it earns balloons[left] * balloons[k] * balloons[right], and the sub-intervals (left, k) and (k, right) are solved independently.
Pad the array with 1's on both ends so boundaries always exist.
dp[left][right] = max over k in (left, right) of
balloons[left]*balloons[k]*balloons[right] + dp[left][k] + dp[k][right]
Fill by increasing interval length; the answer is dp[0][n+1].
Worked example
nums = [3,1,5,8] → padded [1,3,1,5,8,1]. Optimal order gives 167 coins.
Complexity
- Time: O(n^3).
- Space: O(n^2).
Implementation
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] balloons = new int[n + 2];
balloons[0] = 1;
balloons[n + 1] = 1;
for (int i = 0; i < n; i++) balloons[i + 1] = nums[i];
int size = n + 2;
int[][] dp = new int[size][size];
for (int length = 2; length < size; length++) {
for (int left = 0; left + length < size; left++) {
int right = left + length;
for (int k = left + 1; k < right; k++) {
int gain = balloons[left] * balloons[k] * balloons[right];
dp[left][right] = Math.max(dp[left][right],
gain + dp[left][k] + dp[k][right]);
}
}
}
return dp[0][size - 1];
}
}