戳气球

1. 题目描述

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

2. 思路

1. 思路一
   • DFS：每访问一个index，那么左侧和右侧找出未戳的气球
   • 使用set记录已戳过的气球
2. 思路二
   • DFS+缓存

3. 实现

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+缓存

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. 参考

• 逆向思维，从暴力回溯到记忆化 - 戳气球 - 力扣（LeetCode）