312. Burst Balloons

This is a similar problem to matrix chain multiplication. This can be solved by divide-and-conquer with memorization. The basic idea behind is:

Let dp[i][j] to record the maximum sum for interval nums[i, j]. So for subinterval nums[start, end], if we need to pop out nums[k] in nums[start, end], the maximum sum for poping out nums[k] is dp[start][i-1] + nums[k]*nums[start-1]*nums[end+1]+dp[i+1][end]. Note nums[k] is the last element that need to pop out from nums[start, end], so the product should be nums[k]*nums[start-1]*nums[end+1]. dp[i][j] can be calculated recursively.

1:  class Solution {  
2:  public:  
3:    int maxCoins(vector<int>& nums) {  
4:      // let nums to have nums[-1] = nums[n] = 1  
5:      nums.insert(nums.begin(), 1);  
6:      nums.push_back(1);  
7:      vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), INT_MIN));  
8:      return helper(dp, nums, 0, nums.size()-1);  
9:    }  
10:    // note start "s" and end "e" constructs an exclusive interval (s, e)  
11:    int helper(vector<vector<int>> &dp, vector<int> &nums, int s, int e) {  
12:      if (dp[s][e] != INT_MIN) return dp[s][e];  
13:      if (e - s == 1) { dp[s][e] = 0; return 0; }  
14:      int res = 0;  
15:      for (int i = s + 1; i < e; i++) {  
16:        res = max(res, helper(dp, nums, s, i) + helper(dp, nums, i, e) + nums[i]*nums[s]*nums[e]);  
17:      }  
18:      dp[s][e] = res;  
19:      return res;  
20:    }  
21:  };