leetcode 312. 戳气球

题目描述

有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。
现在要求你戳破所有的气球。每当你戳破一个气球 i 时,你可以获得 nums[left] nums[i] nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。

说明:

  • 你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:

输入: [3,1,5,8]
输出: 167 
解释: nums = [3,1,5,8] --> [3,5,8] -->  [3,8] --> [8] --> []
     coins =  3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

题解

动态规划,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]
}