C++(Using Matrix Chain Multiplication)
Please Upvote if you like the Solution!\n\nC++\n\n    class Solution {\n    public:\n    int MCM(vector& nums, int left,int right, vector>& mem)//Matrix Chain M
**Please Upvote if you like the Solution!**\n\n**C++**\n\n    class Solution {\n    public:\n    int MCM(vector<int>& nums, int left,int right, vector<vector<int>>& mem)//Matrix Chain Multiplication Problem\n    {\n        if(left>=right)//Invalid Condition\n            return 0;\n        \n        if(mem[left][right]!=-1)\n            return mem[left][right];\n        \n        int max_cost=INT_MIN;\n        \n        for(int k=left;k<right;k++)//Start iterating from left(1) to right(n-1)\n        {\n           int total_cost=MCM(nums,left,k,mem)+MCM(nums,k+1,right,mem)+nums[left-1]*nums[k]*nums[right];  //after traversing any element from left to right, \n\t\t   //Assume that the traversed element is no more in nums array and find product of current element and its adjacent element\n            \n           max_cost=max(max_cost,total_cost);\n           \n            mem[left][right]=max_cost;\n        }\n       return mem[left][right];\n    }\n    int maxCoins(vector<int>& nums) \n    {\n        nums.insert(nums.begin(),1);//for inserting value in front of vector array by vec_name.insert(pos,val);\n        nums.push_back(1);//Inserting 1 at the end of nums vector array\n        \n        int n=nums.size();\n        vector<vector<int>> mem(n,vector<int>(n,-1));\n        \n        return MCM(nums,1,n-1,mem);\n    }\n    };\n\t\n**Java**\n\t\n\tpublic class Solution {\n    public int maxCoins(int[] nums) {\n        int n = nums.length;\n        \n        // Extend the input array with 1s at both ends\n        int[] newArr = new int[n + 2];\n        newArr[0] = 1;\n        newArr[n + 1] = 1;\n        for (int i = 1; i <= n; i++) {\n            newArr[i] = nums[i - 1];\n        }\n        \n        int m = newArr.length;\n        \n        int[][] dp = new int[m][m];\n        \n        // Initialize dp array with -1 to indicate that values have not been computed yet.\n        for (int i = 0; i < m; i++) {\n            Arrays.fill(dp[i], -1);\n        }\n        \n        // Call the recursive function to find the maximum coins.\n        return matrixChainMultiplication(1, m - 1, newArr, dp);\n    }\n    \n    private int matrixChainMultiplication(int left, int right, int[] nums, int[][] mem) {\n        // If left index is greater than or equal to right, there are no matrices to multiply, return 0.\n        if (left >= right)\n            return 0;\n    \n        // If this subproblem has already been solved, return the previously computed result.\n        if (mem[left][right] != -1)\n            return mem[left][right];\n\n        int max_cost = Integer.MIN_VALUE;\n\n        for (int k = left; k < right; k++) {\n            // Calculate the total cost for multiplying matrices from left to right through index k.\n            int total_cost = matrixChainMultiplication(left, k, nums, mem) + \n                             matrixChainMultiplication(k + 1, right, nums, mem) + \n                             nums[left - 1] * nums[k] * nums[right]; \n\n            // Update the maximum cost found so far.\n            max_cost = Math.max(max_cost, total_cost);\n        }\n\n        // Store the result in the memoization table for future reference.\n        mem[left][right] = max_cost;\n        return mem[left][right];\n    }\n\t}\n\t\n
['Dynamic Programming', 'Memoization', 'C', 'Matrix', 'C++', 'Java']