Bottom Up C++ solution.


  • 0
    P
        int left(vector<int> num,int ind)
        {
            if(ind==-1||ind==num.size())  return 1;
            return num[ind];
        }
    public:
        int maxCoins(vector<int>& nums) {
            int n=nums.size();
            int i,j,k,len;
            long long dp[501][501];
            for(i=0;i<n;i++)    
            {
               dp[i][i]=nums[i]*left(nums,i-1)*left(nums,i+1);
               dp[i][i-1]=0;
            }
            dp[n][n-1]=0;
            for(len=2;len<=n;len++)
            {
                for(i=0;i<n-len+1;i++)
                {
                    dp[i][i+len-1]=INT_MIN;
                    for(k=i;k<=i+len-1;k++)
                    {
                        dp[i][i+len-1]=max(dp[i][i+len-1],dp[i][k-1]+dp[k+1][i+len-1]+nums[k]*left(nums,i-1)*left(nums,i+len));
                    }
                }
            }
            return dp[0][n-1];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.