描述

有n个气球，编号为0到n-1，每个气球都有一个分数，存在nums数组中。每次吹气球i可以得到的分数为 nums[left] * nums[i] * nums[right]，left和right分别表示i气球相邻的两个气球。当i气球被吹爆后，其左右两气球即为相邻。要求吹爆所有气球，得到最多的分数。

1.假设nums[-1] = nums[n] = 1。-1和n位置上的气球不真实存在，因此不能吹爆它们。
2.0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

样例

样例 1:

输入：[4, 1, 5, 10]
输出：270
解释：
nums = [4, 1, 5, 10] 吹爆 1, 得分 4 * 1 * 5 = 20
nums = [4, 5, 10]   吹爆 5, 得分 4 * 5 * 10 = 200 
nums = [4, 10]   吹爆 4, 得分 1 * 4 * 10 = 40
nums = [10]   吹爆 10, 得分 1 * 10 * 1 = 10
总得分 20 + 200 + 40 + 10 = 270
样例 2:

输入：[3,1,5]
输出：35
解释：
nums = [3, 1, 5] 吹爆 1, 得分 3 * 1 * 5 = 15
nums = [3, 5] 吹爆 3, 得分 1 * 3 * 5 = 15
nums = [5] 吹爆 5, 得分 1 * 5 * 1 = 5
总得分 15 + 15 + 5  = 35

思路：

表示到之间的气球被吹爆（不包括）获得的最大分数。假设气球最后被吹爆，则可以得到递推表达式如下

代表到气球被吹爆得到分数，加上到气球被吹爆得到分数。具体实现如下。

class Solution {
public:
    /**
     * @param nums: A list of integer
     * @return: An integer, maximum coins
     */
    int maxCoins(vector<int> &nums) {
        // write your code here
        int n=nums.size();
        if(!n)
        {
            return 0;
        }
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        vector<vector<int>> dp(n+2,vector<int>(n+2,0));
        for(int i=1;i<=n;i++)
        {
            dp[i-1][i+1]=nums[i-1]*nums[i]*nums[i+1];
        }
        for(int len=4;len<=n+2;len++)
        {
            for(int i=0;i<=n+2-len;i++)
            {
                int j=i+len-1;
                for(int m=i+1;m<j;m++)
                {
                    dp[i][j]=max(dp[i][j],dp[i][m]+dp[m][j]+nums[i]*nums[j]*nums[m]);
                }
            }
        }
        return dp[0][n+1];
    }
};