java easy solution done in MCM dp
\nHAPPY NEW YEAR TO MY LEETCODE FAMILY\n\nso this problem can be solved using MCM but a small trick there if u start busting the balloon  from the very start th
```\nHAPPY NEW YEAR TO MY LEETCODE FAMILY\n\nso this problem can be solved using MCM but a small trick there if u start busting the balloon  from the very start then it will so happen that every one will be dependent on the other  say if u burst 5 first then 1*5*8 and the 1 which will be depenedent on the other sub problem that is 8*1*3 so to store it in dp is pretty impossible so we start from bursting last by bursting last i mean \nsuppose u have 3 1 5 8\nyou bursterd 8 last the what will the subproblems (3 1 5)+(empty)+8*1*1\nyou then bursted 3 before busting 8 which result into (3*1*8)+(empty)+(1 5)\nyou then bursted 5 so (5*3*8)+empty+(1)\nand then you bursted 1 so u get 1*3*5+empty +emty \nadd all u will get 167\nthank you for reading my logic i wish u like the way i wrote this if u have any doubt smash it on comment section i have attached the code for clarity\n```\n\n\n```\n\n\nclass Solution \n{\n    public static int mcm(int[] nums,int i,int j,int n,int dp[][])\n    {\n        if(i>j)\n        {\n           return 0;\n        }\n        if(dp[i][j]!=-1)\n        {\n            return dp[i][j];\n        }\n        int left=i-1>=0?nums[i-1]:1;\n        int right=j+1<n?nums[j+1]:1;\n        \n        int max=0;        \n       \n        for(int k=i;k<=j;k++)\n        {\n            max=Math.max(left*nums[k]*right+mcm(nums,i,k-1,n,dp)+mcm(nums,k+1,j,n,dp),max);\n        }\n        return dp[i][j]=max;\n    }\n    public int maxCoins(int[] nums) \n    {\n        int n=nums.length;\n        int dp[][]=new int[n+1][n+1];\n        for(int i=0;i<=n;i++)\n        {\n            Arrays.fill(dp[i],-1);\n        }\n        return mcm(nums,0,nums.length-1,n,dp);\n    }\n}\n```\n\n\n\n\n\n**pls upvote which motivates me to write more for my family**
['Dynamic Programming', 'Java']