题目来源
怎么扎气球才能使得自己获得的硬币最多。
我只能想到中间的从小到大扎，最后把两边的从小到大扎。但是怎么用DP来做呢？想不到，看答案吧。
这道题也得从后往前推，想不到啊想不到，因为扎最后一个的时候，它的左右两边是确定的。所以可以有这么一个关系转移，
dp[left][right] = max(dp[left][right], dp[left][i] + dp[i][right] + nums[left] * nums[i] * nums[right])
代码如下：
class Solution {
public:
int maxCoins(vector<int>& nums) {
vector<int> newNums;
newNums.push_back(1);
for (int num : nums)
newNums.push_back(num);
newNums.push_back(1);
int n = newNums.size();
vector<vector<int>> dp(n, vector<int>(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],
dp[left][i]+dp[i][right]+newNums[left]*newNums[i]*newNums[right]);
}
return dp[0][newNums.size()-1];
}
};
