312.Burst Balloons

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 ballooni 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 1671

    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

Credits:
Special thanks to @peisi for adding this problem and creating all test cases.

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n=nums.size();
        nums.insert(nums.begin(),1);
        nums.insert(nums.end(),1);
        vector<vector<int>>dp(n+2,vector<int>(n+2,0));
        //dp[i][j]表示i到j求得的最大coin值
        for(int len=1;len<=n;len++){//计算的气球下标范围长度
            for(int start=1;start<=n-len+1;start++){//气球下标开始的位置范围
                int end=start+len-1;//气球下标结束的位置
                for(int x=start;x<=end;x++){
                    dp[start][end]=max(dp[start][end],dp[start][x-1]+nums[start-1]*nums[x]*nums[end+1]+dp[x+1][end]);
                }
            }
        }
        return dp[1][n];
    }
};

312.Burst Balloons

原文：http://www.cnblogs.com/zhoudayang/p/5042976.html