本文共 1063 字,大约阅读时间需要 3 分钟。
题目描述
有 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 = 315 + 358 + 138 + 181 = 167来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/burst-balloons 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。C++
class Solution { /* 每个球都会被戳到,就是戳的顺序不同,会造成最后的硬币数不同 方法一:自底向上的动态规划 令 dp[i][j] 表示填满开区间 (i,j) 能得到的最多硬币数, */public: int maxCoins(vector & nums) { if(nums.size()==0) return 0; int len=nums.size(); vector> dp(len + 2, vector (len + 2)); vector new_nums(len+2); //初始化 new_nums[0]=1; new_nums[len+1]=1; for(int i=1;i<=len;i++) new_nums[i]=nums[i-1]; //填表 for(int i=len-1;i>=0;i--) for(int j=i+2;j<=len+1;j++) for(int k=i+1;k