Easy Solution Using Matrix Chain Multiplication
Complexity\n- Time complexity:O(n n n)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(n*n)\n Add your space complexity here, e.g. O(n) \n\n
# Complexity\n- Time complexity:O(n *n *n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n*n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxCoins(vector<int>& nums) {\n        int n = nums.size();\n        nums.insert(nums.begin(), 1);\n        nums.push_back(1);\n        vector<vector<int>> dp(n+2, vector<int>(n+2, 0));\n\n        for(int i = n; i>=1; i--){\n            for(int j = 1; j<=n; j++){\n                if(i>j) continue;\n                int maxi = INT_MIN;\n\n                for(int ind = i; ind<=j; ind++){\n                    int coins = nums[i-1]*nums[ind]*nums[j+1];\n                    int remCoins = dp[i][ind-1]+dp[ind+1][j];\n                    maxi = max(coins+remCoins, maxi);\n                }\n                dp[i][j] = maxi;\n            }\n        }\n\n        return dp[1][n];\n    }\n};\n```
['Array', 'Dynamic Programming', 'C++']