312.txt

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int N=nums.size();
        vector<vector<int>>dp(N,vector<int>(N,-1));
        int res=dfs(nums,dp,0,nums.size()-1);
        return res;
    }
    
    int dfs(vector<int>&A,vector<vector<int>>&dp,int l,int r){
        if(l>r)return 0;
        if(dp[l][r]!=-1)return dp[l][r];
        
        int res=0;
        
        for(int i=l;i<=r;i++){
            res=max(res,A[i]*get(A,l-1)*get(A,r+1)+dfs(A,dp,l,i-1)+dfs(A,dp,i+1,r));
        }
        
        dp[l][r]=res;
        return res;
    }
    
    int get(vector<int>&A,int i){
        if(i<0||i>=A.size())return 1;
        return A[i];
    }
};