Burst Balloons

Hard

The problem

nums[i] is the number painted on balloon i. When you burst balloon i you earn nums[i-1] * nums[i] * nums[i+1], using the neighbours that are still there; anything past either end counts as a balloon painted 1. After a burst, its neighbours become next to each other. Return the most coins you can earn by bursting all the balloons in the best order.

Example 1
Input: nums = [3, 1, 5, 8]
Output: 167
Burst 1 (3*1*5 = 15), then 5 (3*5*8 = 120), then 3 (1*3*8 = 24), then 8 (1*8*1 = 8): 15 + 120 + 24 + 8 = 167.
Example 2
Input: nums = [1, 5]
Output: 10
Burst 1 first (1*1*5 = 5), then 5 (1*5*1 = 5).

Limits

1 ≤ len(nums) ≤ 300
0 ≤ nums[i] ≤ 100

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Think about which balloon you burst LAST in a range — then its neighbours are fixed.

The idea

Interval DP on the padded array: dp[l][r] = max over k of dp[l][k] + dp[k][r] + nums[l]·nums[k]·nums[r].

Target: O(n³) time

Go function shape

func maxCoins(nums []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// MaxCoins: interval DP. Choose the balloon k that bursts LAST in (l, r);
// then its neighbours are the fixed ends l and r, and the two sides are independent subproblems.
func MaxCoins(nums []int) int {
	a := append([]int{1}, append(append([]int{}, nums...), 1)...)
	n := len(a)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for length := 2; length < n; length++ {
		for l := 0; l+length < n; l++ {
			r := l + length
			for k := l + 1; k < r; k++ {
				dp[l][r] = max(dp[l][r], dp[l][k]+dp[k][r]+a[l]*a[k]*a[r])
			}
		}
	}
	return dp[0][n-1]
}

Read the lesson: 2-D Dynamic Programming