MaxCoins returns the maximum coins we can collect by bursting the balloons
(nums []int)
| 4 | |
| 5 | // MaxCoins returns the maximum coins we can collect by bursting the balloons |
| 6 | func MaxCoins(nums []int) int { |
| 7 | n := len(nums) |
| 8 | if n == 0 { |
| 9 | return 0 |
| 10 | } |
| 11 | |
| 12 | nums = append([]int{1}, nums...) |
| 13 | nums = append(nums, 1) |
| 14 | |
| 15 | dp := make([][]int, n+2) |
| 16 | for i := range dp { |
| 17 | dp[i] = make([]int, n+2) |
| 18 | } |
| 19 | |
| 20 | for length := 1; length <= n; length++ { |
| 21 | for left := 1; left+length-1 <= n; left++ { |
| 22 | right := left + length - 1 |
| 23 | for k := left; k <= right; k++ { |
| 24 | coins := nums[left-1] * nums[k] * nums[right+1] |
| 25 | dp[left][right] = max.Int(dp[left][right], dp[left][k-1]+dp[k+1][right]+coins) |
| 26 | } |
| 27 | } |
| 28 | } |
| 29 | |
| 30 | return dp[1][n] |
| 31 | } |