Problem

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

问题描述

给定 n 个气球，标号从 0 到 n-1。每个气球上都有一个非负的数字，用 nums 数组表示。你需要引爆所有的气球，如果你引爆气球 i，你会得到 nums[left]*nums[i]*nums[right] 个金币。这里的 left 和 right 是 i 的邻近元素。在爆炸之后，left 和 right 会变成邻近的元素。求你能获取到的最大金币数。

备注

1. 你可以认为 nums[-1]=nums[n]=1，但是这并不能够引爆
2. n 在 0 到 500 之间
3. nums[i] 在区间 [0, 100]

样例

输入: [3, 1, 5, 8]
输出: 167
解释: 首先引爆 1，获得金币 15，数组变为 [3, 5, 8]。其次引爆 5，获得金币 120，数组变为 [3, 8]。
     再次引爆 3，获得金币 24，数组变为 [8]。最后引爆 8，获得金币 8。总金币为 15+120+24+8=167，
     为可能获取到的最大金币数。

解法 1

按照提示，我们需要在 nums 这个数组的前后添加元素 1。这样可以保证在爆炸第一个元素或最后一个元素时，可以直接在 for 循环中进行处理，而不用单独进行处理。

既然是要求获得最大的金币数，那么我们可以使用动态规划解决这个问题。我们需要使用一个数组 dp 来保留中间结果。dp[i][j] 表示将原数组中引爆第 i 个气球到第 j 个气球得到的最大金币。

下面我们考虑如何计算 dp[i][j]。要计算引爆第 i 个气球到第 j 个气球产生最大金币，我们遍历一下最后引爆的气球。如果 k 是最后引爆的气球，那么我们需要引爆第 i 个气球到第 k-1 个气球，引爆第 k+1 个气球到第 j 个气球，分别得到 dp[i][k-1] 及 dp[k+1][j] 个金币。同时，引爆第 k 个气球，我们可以得到 nums[i-1]*nums[k]*nums[j+1] 个金币，故