leetcode-go/leetcode/hard/312.burst-balloons.go

func maxCoins(nums []int) int {
	n := len(nums) + 2
	arr := make([]int, n)
	copy(arr[1:], nums)
	arr[0], arr[n-1] = 1, 1
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	} // dp[l][r] means the maximum coins one can get from (l, r) (l, r not included)
	for k := 2; k < n; k++ {
		for l := 0; l < n-k; l++ {
			r := l + k
			for i := l + 1; i < r; i++ {
				if coins := arr[l]*arr[i]*arr[r] + dp[l][i] + dp[i][r]; dp[l][r] < coins {
					dp[l][r] = coins
				}
			}
		}
	}
	return dp[0][n-1]
}