LeetCode-312. Burst Balloons

LeetCode-312. Burst Balloons

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​​

题解：

class Solution {public: int maxCoins(vector& nums) { nums.insert(nums.begin(), 1); nums.push_back(1); int n = nums.size(); vector> dp(n, vector(n, 0)); for (int k = 2; k < n; k++) { for (int left = 0; left < n - k; left++) { int right = left + k; for (int i = left + 1; i < right; ++i) { dp[left][right] = max(dp[left][right], nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]); } } } return dp[0][n - 1]; }};

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