Code
ì œì¶œ ë‚ ì§œ | 시간 | 메모리 |
2021/01/03 | 1968 ms | 17.3 MB |
// 312. Burst Ballons
//
// https://leetcode.com/problems/burst-balloons/
// maxCoins function returns the maximum values when all balloons bursted in some sequences.
// When i th balloon bursted, then values of i - 1 * i * i + 1 will be producted.
// And then 0 ... i - 1 and i + 1 ... length should be conducted the same logic.
// Picking i th balloon could be divided into the subproblem.
// In the reverse concept, pretend that picking i th ballon is the last balloon to be bursted.
// [ 3 , 1 , 5 , 8 ] ----------> pick 5 as last element to be bursted.
// [ 3 , 1 ] [ 8 ] should be calculated.
// [ 3, 1 ] ----------> same logic on the first case. (pretend x)
// [ 8 ] ----------> same logic on the first case. (pretend y)
// [ 3 , 1 , 5 , 8 ] ----------> x + y + 1 * 5 * 1 will be the coins that this sequence earned.
// Maybe before the last sequence could be optimal, but not in the last sequence.
// Thus, picking the very first element to be last sequence should be searched too.
// n times loop * n times loop for the left range * n times loop for the right range becomes O(n^3).
// Each element for the last sequence should be maintained the n number of elements, so O(n^2) memory required.
func maxCoins(nums []int) int {
vals := append([]int{1}, append(nums, 1)...)
dp := make(map[[2]int]int, 0)
var rangeSearch func(int, int) int
rangeSearch = func(left, right int) int {
if coins, ok := dp[[2]int{left, right}]; ok {
return coins
}
coins := 0
for i := left; i <= right; i++ {
temp := vals[left-1] * vals[i] * vals[right+1]
temp += rangeSearch(left, i-1) + rangeSearch(i+1, right)
if coins < temp {
coins = temp
}
}
dp[[2]int{left, right}] = coins
return coins
}
return rangeSearch(1, len(vals)-2)
}
Go