312. 戳气球

以你之姓@ 2023-02-28 05:44 7阅读 0赞

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums\[left\] \* nums\[i\] \* nums\[right\] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]

来源：力扣（LeetCode）[添加链接描述][Link 1]

反向思考，每次添加一个气球，直到添满得到最大值。  
solve（i，j）表示开区间（i，j）之间添满的最大值。[leetcode题解][leetcode]  
![在这里插入图片描述][20200720162334914.png]

class Solution {
        
    public:
        vector<vector<int> > rec;
        vector<int> val;
    
        int solve(int left, int right){
        
            if(left >= right-1) return 0;
            if(rec[left][right] != -1) return rec[left][right]; //用数组记录，防止重复计算
            for(int mid = left+1; mid < right; mid++){
        
                int temp = val[left]*val[mid]*val[right];
                temp += solve(left, mid);
                temp += solve(mid, right);
                rec[left][right] = max(temp, rec[left][right]);
            }
            return rec[left][right];
        }
    
        int maxCoins(vector<int>& nums) {
        
            int n = nums.size();
            rec.resize(n+2, vector<int>(n+2, -1));
            val.resize(n+2);
            for(int i = 1; i <= n; i++) val[i] = nums[i-1];
            val[0] = val[n+1] = 1;
            return solve(0, n+1);
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]: /images/20230209/4a9b11fcbfaf49c683940720499d0794.png
[Link 1]: https://leetcode-cn.com/problems/burst-balloons
[leetcode]: https://leetcode-cn.com/problems/burst-balloons/solution/chuo-qi-qiu-by-leetcode-solution/
[20200720162334914.png]: /images/20230209/d80343275cc74be18f6be121b170a4a2.png