[leetcode] 312. Burst Balloons

[leetcode] 312. Burst Balloons

Description

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them. 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100 Example:

Input: [3,1,5,8]Output: 167 Explanation: 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

分析

题目的意思是： 给你一组气球，球上面有数字，如果你扎破其中的一个球，你会得到这个气球和左右相邻气球相乘值的硬币。现在要求你能得到的最大的硬币数

这道题目是leetcode上面的hard难度的题目，我应该做不出来，所以就没为难自己了，直接上别人的代码.题目中说明了边界情况，当气球周围没有气球的时候，旁边的数字按1算，这样我们可以在原数组两边各填充一个1，这样方便于计算。这道题的最难点就是找递归式，如下所示：

dp[l][r] = max(dp[l][r], nums[l ]*nums[k]*nums[r] + dp[l][k] + dp[k][r]) dp[l][r]表示扎破(l, r)范围内所有气球获得的最大硬币数，不含边界

代码

class Solution {public: int maxCoins(vector& nums) { vector temp(nums.size()+2,0); int n=1; for(auto num:nums){ if(num>0){ temp[n]=num; n++; } } temp[0]=temp[n]=1; n++; int dp[n][n]={}; for(int k=2;k

参考文献

​​312. Burst Balloons​​​​LeetCode[312] Burst Balloons​​​​[LeetCode] Burst Balloons 打气球游戏​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。