Short C++ dynamic programming solution


  • 0
    G
    class Solution {
    public:
        int maxCoins(vector<int>& nums) 
        {
            vector<int> New(nums.size() + 2,1);
            vector<vector<int> > D(New.size(),vector<int>(New.size(),0));
            
            std::copy(nums.begin(),nums.end(),New.begin() + 1);
    
            for(int i = 1; i < New.size() - 1; ++i)
            {
                for(int j = i; j >= 1; --j)
                {
                    for(int k = j; k <= i; ++k)
                    {
                        D[j][i] = max(D[j][i],New[k]*New[j - 1]*New[i + 1] + (j < k ? D[j][k - 1] : 0) + (i > k ? D[k + 1][i] : 0));
                    }
                }
            }
            
            return D[1][New.size() - 2];
        }
    };

Log in to reply
 

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