leetcode 312. 戳气球

题解

动态规划,dp[i][j]表示戳爆从ij个气球的最大金币数,依次戳爆1、2、3…n个气球,最终得到dp[1][n]表示最大金币数

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func maxCoins(nums []int) int {
n := len(nums)
dp := make([][]int, n+2)
for i := 0; i < n+2; i++ {
dp[i] = make([]int, n+1)
}
nums = append(nums, 1)
nums = append([]int{1}, nums...)
for m := 1; m <= n; m++ {
for i := 1; i <= n-m+1; i++ {
j := i+m-1
for k := i; k <= j; k++ {
sum := nums[i-1] * nums[k] * nums[j+1] + dp[i][k-1] + dp[k+1][j]
if dp[i][j] < sum {
dp[i][j] = sum
}
}
}
}
return dp[1][n]
}