LeetCode 312. Burst Balloons

原题链接：https://leetcode.com/problems/burst-balloons/

这是一道比较复杂的动态规划问题，关键在于定义好独立的子问题。

原问题可以转化为求f(i, j)的最大值，当i == 0 && j == n时，就是我们要的答案。

把j逐次向后移动，依次求f(0, 1), f(0, 2)... f(0, n)的最大值。

求f(0, j)的最大值，可以转化为子问题：在0..j中找到元素k，当k是最后一个戳破时，f(1, k-1) + f(k+1, j) + num[0] * num[k] * num[j+1]值最大。

更进一步的思考:

1. 为什么最后一定是num[0] * num[k] * num[j+1]？如果是num[i]*num[k]*num[j+1]构成最大呢？其实这种情况已经被k = i-1这种case考虑过了：

2. 怎样找到max(f(1, k-1) + f(k+1, j) + num[0] * num[k] * num[j+1])？

我们可以令i = j-1..1，然后让k = j..i+1，找到使得f(i,j) = f(i+1, k-1) + f(k+1, j) + num[i] * num[k] * num[j + 1]  最大的k。因为i是从j-1向1移动的，所以每次可以利用前一轮计算的结果，也就是说f(i+1, k-1) 和 f(k+1, j)其实之前已经计算过。

因为每次j移动时，会对之前的乘积造成影响，所以需要重新计算一遍f(i, j)。

代码如下：

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        if(nums.size() == 0){
            return 0;
        }
        if(nums.size() == 1){
            return nums[0];
        }
        
        int size = nums.size();
        nums.push_back(1);
        nums.insert(nums.begin(), 1);
        vector<vector<int>> mem(size + 1, vector<int>(size + 1, 0));
        mem[1][1] = nums[1]*nums[2];
        mem[size][size] = nums[size-1]*nums[size];
        for(int i = 2; i < size; i++){
            mem[i][i] = nums[i-1]*nums[i]*nums[i+1];
        }
        for(int j = 2; j <= size; j++){
            for(int i = j - 1; i >=1; i--){
                for(int k = j; k >= i; k--){
                    int product = nums[k] * nums[i-1] * nums[j+1];
                    int left = i < k ? mem[i][k-1]:0; 
                    int right = j > k? mem[k+1][j]:0; 
                    int sum = product + left + right;
                    mem[i][j] = max(sum, mem[i][j]);
                }
            }
        }
        
        return mem[1][size];
    }
};