Clean Iterative O(N^3) C++ solution using DP


  • 1
    J
    class Solution {
    public:
        int maxCoins(vector<int>& nums) {
            vector<int> v;
            v.push_back(1);
            v.insert(v.end(), begin(nums), end(nums));
            v.push_back(1);
            int n = v.size();
            
            vector<vector<int>> dp(n, vector<int>(n, 0));
            
            for (int l = 3; l <= n; l++)
                for(int i = 0; i + l - 1 < n; i++)
                    for (int k = i + 1; k < i + l - 1; k++)
                        dp[i][i + l - 1] = max(dp[i][i+l-1], dp[i][k] + dp[k][i+l-1] + v[k] * v[i] * v[i+l-1]);
            
            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.