## Monday, August 7, 2017

### [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题，很有意思。

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

[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:    }
``````