312.Burst Balloons

class Solution {  
public:  
    int maxCoins(vector<int>& nums) {  
        int arr[nums.size()+2];  
          
        for(int i=1;i<nums.size()+1;++i)arr[i] = nums[i-1];  
        arr[0] = arr[nums.size()+1] = 1;  
          
        int dp[nums.size()+2][nums.size()+2]={};  
        int n = nums.size()+2;  
          
        for(int k=2;k<n;++k)  
        {  
            for(int left = 0;left<n-k;++left){  
                int right = left + k;  
                for(int i=left+1;i< right; ++i)  
                {  
                    dp[left][right] = max(dp[left][right],arr[left]*arr[i]*arr[right] + dp[left][i] + dp[i][right]);  
                }  
            }      
        }  
        return dp[0][n-1];  
    }  
};

dfs暴力求解：

class Solution {
    vector<bool> visited;
    int res;
    int n;
    
    int findLeft(int i){
        int j = i - 1;
        while(j >= 0 && visited[j]) j--;
        return j;
    }
    
    int findRight(int i){
        int j = i + 1;
        while(j < n && visited[j]) j++;
        return j;
    }
    
    void helper(vector<int>& nums, int left, int coin){
        if(left == 0) {
            res = max(res, coin);
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                int li = findLeft(i);
                int ri = findRight(i);
                int l = li < 0 ? 1:nums[li];
                int r = ri >= n ? 1:nums[ri];
                int m = l*nums[i]*r;
                helper(nums, left - 1, coin + m);
                visited[i] = false;
            }
        }
    }
    
public:
    int maxCoins(vector<int>& nums) {
        visited.resize(nums.size(),false);
        res = 0;
        n = nums.size();
        helper(nums,n,0);
        return res;
    }
};