赞
踩
有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i个气球,你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界,那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例1
输入:nums = [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
示例2
输入:nums = [1,5]
输出:coins=10
题目来源:力扣(LeetCode)
第n次
的戳破进行递归切入,单凭一维数字n
的话,第n-1次
戳破的状态不好确定,发现不可行。继续思考,如果我们戳破一个气球,那么就会计算刚刚戳破的这个气球与其前后两个气球的数字乘积。[i,j]
,在这两个元素间内最后一次戳破的是元素k(i<k<j)
的话(说明戳破k之后i和j变成相邻状态),那么这次戳破之后就会之前计算的最大值coins基础上继续加上nums[i]* nums[k] * nums[j]
。以此延申,假如[i,j]之间有不止一个元素,也就是除k以外还有元素,那么如何求这个区间[i,j]的最大乘积呢?coins = dp[i][j] = max(dp[i][j],(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]));
其中的dp[i][j]
就表示在区间[i,j]上进行最优化戳破之后得到的最大乘积coins。对公式进行解释就是戳破k右边的所有气球得到的dp[i][k]
和戳破k左边的所有气球得到的最大值dp[k][j]
.dp[i][j
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。