Burst Balloons

1. Problem Description

There are n balloons, numbered from 0 to n - 1. Each balloon has a number written on it, stored in the array nums.

You are asked to burst all the balloons. Bursting balloon i gives you nums[i - 1] * nums[i] * nums[i + 1] coins. Here i - 1 and i + 1 are the indices of the two balloons adjacent to i. If i - 1 or i + 1 is outside the array boundary, treat it as a balloon with value 1.

Find the maximum number of coins you can collect.

2. Approach

1. Approach 1
   • DFS: whenever an index is visited, find the nearest unburst balloons on its left and right
   • Use a set-like visited array to record balloons that have already been burst
2. Approach 2
   • DFS + memoization

3. Implementation

3.1. DFS

const (
    Visited = 1
    UnVisited = 0
)

func maxCoins(nums []int) int {
    visited := make([]byte, len(nums))
    return maxCoinsDFS(nums, 0, visited)
}

func maxCoinsDFS(nums []int, index int, visited []byte) int {
    if index >= len(nums) {
        return 0
    }

    count := 0
    for i := 0; i < len(nums); i++ {
        if visited[i] == Visited {
            continue
        }
        visited[i] = Visited
        amount := getAmount(nums, i, visited) + maxCoinsDFS(nums, index+1, visited)
        count = max(count, amount)
        visited[i] = UnVisited
        
    }

    return count
}

func getAmount(nums []int, index int, visited []byte) int {
	leftCount := 1
	for left := index - 1; left >= 0; left-- {
		if visited[left] == UnVisited {
			leftCount = nums[left]
			break
		}
	}

	rightCount := 1
	for right := index + 1; right < len(nums); right++ {
		if visited[right] == UnVisited {
			rightCount = nums[right]
			break
		}
	}

	return leftCount * nums[index] * rightCount
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

3.2. DFS + Memoization

func maxCoins(nums []int) int {
    a := make([]int, len(nums)+2)
    a[0] = 1
    a[len(a)-1] = 1
    for i := 0; i < len(nums); i++ {
        a[i+1] = nums[i]
    }

    memo := make([][]int, len(a))
    for i:=0; i<len(memo);i++{
        memo[i] = make([]int, len(a))
    }
    for i := 0; i < len(memo);i++ {
        for j := 0; j<len(memo); j++ {
            memo[i][j] = math.MinInt32
        }
    }
    return maxCoinsDFS(a, 0, len(a)-1, memo)
}

func maxCoinsDFS(a []int, i, j int, memo [][]int) int {
    if memo[i][j] != math.MinInt32 {
        return memo[i][j]
    }

    max := 0
    for k := i+1; k < j; k++ {
        max = Max(max, maxCoinsDFS(a, i, k, memo)+a[i]*a[k]*a[j] +  maxCoinsDFS(a, k, j, memo))
    }
    memo[i][j] = max
    return max
}


func Max(a, b int) int {
    if a>b{
        return a
    }
    return b
}

4. References

• Reverse Thinking: From Brute-Force Backtracking to Memoization - Burst Balloons - LeetCode