[Leetcode] Burst Balloons, Solution

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

[Thoughts]
DP题，很有意思。

假设K是range(i,j)中最后一个被戳破的气球，那么我们可以得到

DP[i][j] = max( DP[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + DP[k+1][j])      i<k<j

在计算的过程中从底向上，len是1到n来计算。


[Code]

1:    int maxCoins(vector<int>& nums) {  
2:        
3:      int n = nums.size();  
4:      // add boundary to simplify the corner case  
5:      nums.insert(nums.begin(), 1);  
6:      nums.push_back(1);  
7:        
8:      vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));  
9:        
10:      for(int len = 1; len<=n; len++) {  
11:        for(int left = 1; left<=n-len +1; left++) {  
12:          int right = left + len -1;  
13:          for(int k =left; k<=right; ++k) {  
14:            // K is the Balloons destroyed in the last  
15:            dp[left][right] = max(  
16:              dp[left][right],   
17:              nums[left-1]*nums[k]*nums[right+1] + dp[left][k-1] + dp[k+1][right],  
18:            );  
19:          }  
20:        }  
21:      }  
22:      return dp[1][n];  
23:    }