C++ easy recursive solution with explnation
This question is a variation of matrix multiplication problem. In that problem we need to find the minimum cost of multiplying the matrices. In this we have to 
This question is a variation of matrix multiplication problem. In that problem we need to find the minimum cost of multiplying the matrices. In this we have to found the maximum instead of minimum.. First, we need to add one element in left side and right side of the array. Now we need to find the maximum cost by moving K from i to j.\n\n\n```\nclass Solution {\npublic:\n    int maxCoins(vector<int>& nums) {\n        if(nums.size()==0)\n            return 0;\n        vector<int> v(nums.size()+2,1);\n        for(int i=0;i<nums.size();i++)\n        {\n            v[i+1]=nums[i];\n        }\n        vector<vector<int>> dp(v.size(),vector<int> (v.size(),-1));\n        return helper(v,1,v.size()-1,dp);\n    }\n    \n    int helper(vector<int> &v, int i, int j,vector<vector<int>> &dp)\n    {\n        if(i>=j)\n            return 0;\n        if(dp[i][j]>=0)\n            return dp[i][j];\n        int cost=INT_MIN;\n        for(int k=i;k<=j-1;k++)\n        {\n            cost=max(cost, helper(v,i,k,dp)+helper(v,k+1,j,dp)+ v[i-1]*v[k]*v[j]);\n        }\n        dp[i][j]=cost;\n        return cost;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']