312. 戳气球

自上而下

戳气球会导致左右邻居的移动，因此将问题转化为添加气球

helper(i, j)表示在i~j这个开区间内添加气球，之所以开区间是因为左右区间设置为边界外，那里的气球是不能戳的，可以考虑到。

然后寻找这个区间添加后值最大的气球，对左右两边继续进行添加，对于每个区间，都会遍历每个值，然后对左右两边进行递归，从而求出

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        vector<int> val(nums.size() + 2, 1);
        vector<vector<int>> memo(nums.size() + 2, vector<int>(nums.size() + 2, -1));
        for(int i = 0; i < nums.size(); ++i)
            val[i + 1] = nums[i];
        return helper(0, nums.size() + 1, memo, val);
    }
private:
    int helper(int lo, int hi, vector<vector<int>>& memo, vector<int>& val)
    {
        if(lo >= hi - 1) // 注意这个，由于是开区间，所以当left和right相差1时，内部已经没有元素了，所以返回
            return 0;
        if(memo[lo][hi] != -1)
            return memo[lo][hi];
        for(int i = lo + 1; i < hi; ++i)
        {
            auto pro = val[lo] * val[i] * val[hi];
            pro += helper(lo, i, memo, val) + helper(i, hi, memo, val);
            memo[lo][hi] = max(memo[lo][hi], pro);
        }
        return memo[lo][hi];
    }
};

自下而上

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        vector<int> val(nums.size() + 2, 1);
        vector<vector<int>> memo(nums.size() + 2, vector<int>(nums.size() + 2, 0));
        for(int i = 0; i < nums.size(); ++i)
            val[i + 1] = nums[i];
        // 从后面往前，小区间逐渐计算到大区间，之所以要从后往前，是因为如果从前往后的话，那就从大到校了
        for(int i = nums.size() - 1; i >= 0; --i)
        {
            // 从i + 2，开始，因为i和j间必须存在一个元素
            for(int j = i + 2; j < nums.size() + 2; ++j)
            {
                // 遍历
                for(int k = i + 1; k < j; ++k)
                {
                    auto pro = val[i] * val[k] * val[j];
                    // i ~ k 和 k ~ j都是在已经遍历过的区间内
                    // 由于k<j,所以memo[k]已经可以从之前的i，j遍历结果出来了，当没有元素时候就是0，是base，而k>i，所以memo[k][j]也可以从之前的结果出来了
                    pro += memo[i][k] + memo[k][j];
                    memo[i][j] = max(memo[i][j], pro);
                }
            }
        }
        return memo[0][nums.size() + 1]; // 返回最大区间的解
    }
};