[C++知识库]Burst Balloons（C++戳气球）

(1) dp

class Solution {
public:
    
    int helper(vector<int>& nums,vector<vector<int>> &v,int l,int r) {
        if(l>=r-1) return 0;
        if(v[l][r]!=-1) return v[l][r];
        
        for(int i=l+1;i<r;i++) {
            v[l][r]=max(v[l][r],nums[l]*nums[i]*nums[r]+helper(nums,v,l,i)+helper(nums,v,i,r));
        }
        return v[l][r];
    }
    
    int maxCoins(vector<int>& nums) { 
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        
        int n=nums.size();
        vector<vector<int>> v(n,vector<int>(n,-1));
        return helper(nums,v,0,n-1);
    }
};