leetcode312

Overview ¶

* @lc app=leetcode id=312 lang=golang * * [312] Burst Balloons * * https://leetcode.com/problems/burst-balloons/description/ * * algorithms * Hard (50.66%) * Likes: 2116 * Dislikes: 58 * Total Accepted: 90.1K * Total Submissions: 177.9K * Testcase Example: '[3,1,5,8]' * * 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 *