前言
持续更新了
正文
问题来源
本问题来自leetcode上的312题。
问题描述
有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
示例 1:
输入: [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
分析：
矩阵连乘问题，要注意的是左右边界要加上为1的单元，并且是连乘最大的问题。
func max(a, b int) int {
if a > b {
return a
}
return b
}
func maxCoins(nums []int) int {
cnums := make([]int, 0, len(nums)+2)
cnums = append(cnums, 1)
cnums = append(cnums, nums...)
cnums = append(cnums, 1)
n := len(nums)+2
dp := make([][]int, len(nums)+2)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
}
for r := 2; r < n; r++ {
for i := 1; i < n-r+1; i++ {
j := r-1+i
tmp := 0
for k := i; k < j; k++ {
tmp = max(tmp, dp[i][k]+dp[k+1][j]+cnums[i-1]*cnums[k]*cnums[j])
}
dp[i][j] = tmp
}
}
return dp[1][n-1]
}
总结：
勤思考。
结语
不管怎么样好好加油。
