题目描述
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: (1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them. (2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:
Given [3, 1, 5, 8]
Return 167
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 大意：寻找戳破气球的最优解，使得分最高，计分：nums[left] * nums[i] * nums[right]
解题思路一（超时）：
遍历所有计分可能，与当前分数比较，大的话就把新得到的分数替换原来分数，运用for循环遍历所有可能性。很遗憾，超时了，在数组大于10的时候明显效率低下。（但是我还是想把源码贴出来）
/*void burst(vector<int> nums, int i, int& result, int& really) { int re = 0; int left = (i - 1 == -1) ? 1 : nums[i - 1]; int right = (i + 1 == nums.size()) ? 1 : nums[i + 1]; re += (left * right * nums[i]); result += re; nums.erase(nums.begin() + i); for (int u = 0; u < nums.size(); u++) { burst(nums, u, result,really); } if (nums.size() == 0 && result > really) { really = result; } result -= re; } int maxCoins(vector<int>& nums) { if (nums.size() == 0) return 0; int final001 = 0; for (int i = 0; i < nums.size(); i++) { int result = 0; burst(nums, i, result,final001); } //sort(final001.begin(), final001.end()); return final001; }*/
解题思路二：
借鉴其他博客的方法，用到了动态规划：［动态规划背后的基本思想非常简单--大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。引用地址：http://blog.csdn.net/carson2005/article/details/22092969］
［递推的公式需要仔细想一下，需要注意的是气球被打掉就不会再被计算了。我们假设f(i, j)表示一个以i+1为起始位置，j-1终止的sub array能得到的最多coin数量。正着猜第一个气球打哪一个不好猜，于是我们可以倒着猜。假设打的最后一个气球是第k个气球（在[i, j]范围内），也就是说，从第i+1到k-1这个范围内的气球以及从k+1到j-1这个范围内的气球此时已经全被打掉了。那么可以知道，当打掉最后一个气球k时，所得到的coin的数量就是: f(i, k) + f(k, j) + nums[i]* nums[k] * nums[j]。我们猜测每一个k的位置然后取其中的最大值。
引用地址：http://www.hihuyue.com/hihuyue/codepractise/leetcode/leetcode312-burst-balloons］
下面是我的代码以及解释：
int maxCoins(vector<int>& nums) { int many = nums.size(); //(1) nums.insert(nums.begin(), 1); nums.insert(nums.end(), 1); //(2) //dp[i][j] = max(dp[i][j], nums[i]*nums[k]*nums[j] + dp[i][k-1] + dp[k+1][j]) k的范围为[i,j] vector<vector<int> > dp(many+2,vector<int>(many+2,0)); for (int count = 2; count <= many+1; count++) { //(3) for (int i = 0; i <= many - count + 1; i++) { int j = i + count; for (int k = i + 1; k < j; k++) { dp[i][j] = max(dp[i][j], nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]); } } } return dp[0][many+1];//(4) }
注释（1）：
在数组左右加上1，相当于把nums［－1］，nums［n］同时考虑进来，方便许多
注释（2）：
构造了一个二维数组，利用dp［i］［j］表示nums在（i，j）里的最大分，也就是动态规划里，用一张表记录下所有问题的解，以便下次复用。然后，（i，j）从区间里只包含一个数扩大到包含整个数组，结果也就出来了。k 属于 （i，j），也就是最后一个被戳破的，它戳破前，（i，k）和（k，j）已经无气球了，i，j是它的left & right。
注释（3）：
i，j，k 的取值。为了推出 i，j，可以考虑数组只剩下一个数的情形（假设数组原来size ＝ 4），那么，要遍历的k，就可能是 1，2，3，4（0，5都是后来加的1），那么对应的，k ＝ 1，i ＝ 0，j ＝ 2； k ＝ 2， i ＝ 1，j ＝ 3……，还有最后一种情况，1234同时存在，i＝0，j ＝ 5 依次类推得出：
int i = 0; i <= many - count + 1; i++
int j = i + count;
还有一点，是为什么 + dp[i][k] + dp[k][j]， 而不是 + dp[i][k－1] + dp[k＋1][j]
因为 k >= i + 1, k < j，是一个开区间，如果换成后者，k－1，k＋1两个元素都将被排除，结果错误
心得：
1）用二维数组表示区间
2）vector的构造方法：
vector<vector<int> > dp(many+2,vector<int>(many+2,0));
3）动态规划
