Burst balloons recursion with memorization
At first I thought i will try for recursive approach then add memorization to it but I have done a mistake I used arraylist and ost the track of index it is rec
At first I thought i will try for recursive approach then add memorization to it but I have done a mistake I used arraylist and ost the track of index it is recursively correct but time limit exceeded because of O(n!) time complexity then I have changed my storing metho and done simple recursively with memorization.\n```\nclass Solution {\n    public int maxCoins(int[] nums) {\n        ArrayList<Integer> arr=new ArrayList<>();\n        for(int i :nums)\n            arr.add(i);\n        return getMaxCoins(arr,0);\n    }\n\n    public int getMaxCoins(ArrayList<Integer> arr,int ans){\n        if(arr.size()==0)\n            return ans;\n        int max=0;\n        for(int i=0;i<arr.size();i++){\n            int mul=1,val=arr.get(i);\n            if(i!=0) mul*=arr.get(i-1);\n            if(i<arr.size()-1) mul*=arr.get(i+1);\n            int sum=ans+val*mul;\n            arr.remove(i);\n            max=Math.max(max,getMaxCoins(arr,sum));\n            arr.add(i,val);\n        }\n        return max;\n    }\n}\n```\nCode below is recursion with memorization simple as possible.\nFor the above soln we have `nums[i-1]*nums[i]*nums[i+1]` for the below soln we have `nums[-1]*nums[i]*nums[n].` .there are n balloons and `i ` will be the last one to burst.\n\nWe can see that the balloons is again separated into 2 sections. But this time since the balloon `i ` is the last balloon of all to burst, the left and right section now has well defined boundary and do not affect each other.\n\n```\nclass Solution {\n    public int maxCoins(int[] nums) {\n        int n=nums.length;\n        int []extended=new int[n+2];\n        extended[0]=extended[n+1]=1;\n        for(int i=1;i<n+1;i++)\n            extended[i]=nums[i-1];\n        \n        int [][]memoriz=new int[n+2][n+2];\n        return getMaxCoins(extended,memoriz,0,n+1);\n    }\n\n    public int getMaxCoins(int []extended,int [][]memoriz,int left,int right){\n        if(left==right) return 0;\n        if(memoriz[left][right]>0) return memoriz[left][right];\n        int max=0;    \n        for(int i=left+1;i<right;i++)\n            max=Math.max(max,extended[left]*extended[i]*extended[right]+getMaxCoins(extended,memoriz,left,i)\n                         +getMaxCoins(extended ,memoriz,i,right));\n        \n        memoriz[left][right]=max;\n        return max;\n    }\n}\n```\nThe below statement is crux of whole solution `extended[left]*extended[i]*extended[right]` this will account for last step where we have 1 as boundaries. Think in this way we break big problem into two small problems, take an example for n=5 elements **loop will be for 1-5** At `i =1` get ans of 0-1  ->`getMaxCoins(extended,memoriz,left,i)` and 1-5->`getMaxCoins(extended ,memoriz,i,right)` and add them as whole and find the maximum of all taking i=1,2,3,4,5..n as first step and boom we got the ans and in intermediate steps we store values into array for duplicate steps.\n```\nmax=Math.max(max,extended[left]*extended[i]*extended[right]+getMaxCoins(extended,memoriz,left,i)\n                         +getMaxCoins(extended ,memoriz,i,right));\n```\nHere is dp solution too with same intution same explanation with a slider that is used for filling 2D matrix diagonally .DP soln is bit complex if you jump previous parts I had visualize how values are filling in  matrix in memorization and then able to wrote DP soln .\n```\nclass Solution {\n   public int maxCoins(int[] nums) {\n\tint n=nums.length;\n    int []extended=new int[n+2];\n     extended[0]=extended[n+1]=1;\n     for(int i=1;i<n+1;i++)\n         extended[i]=nums[i-1];\n        \n    int[][] dp = new int[n+2][n+2];\n    for (int slider = 2; slider < n+ 2; slider++){\n        for (int left = 0; left < n +2 - slider; left++) {\n            int right = left + slider;\n            for (int i = left + 1; i < right; i++)\n                dp[left][right] = Math.max(dp[left][right],extended[left] * extended[i] * extended[right] \n                                           + dp[left][i] + dp[i][right]);\n            \n        }\n    }\n\n    return dp[0][n +1];\n    }\n}\n```\n**If you like my explaination and hardwork please upvote it,will motivate and inspire me.**
['Java']