HAPPY NEW YEAR | My  Understanding To Solve This Problem || Similar Pattern to Solve Other
HAPPY NEW YEAR \uD83C\uDF89\uD83C\uDF89\n---\nI can assure You that if u solve any dp subarray problem , I can make You understand this problem and You are able
# *HAPPY NEW YEAR* \uD83C\uDF89\uD83C\uDF89\n---\n**I can assure You that if u solve any dp subarray problem , I can make You understand this problem and You are able to write your own code**\n\n---\n\n## Some basic question trying to answer in this post\n**question1** :   Is this problem different from other dp subarray problem or same ?\n**question2** :   How to come up with solution if solved other dp subarrays problem ?\n**question3** :  Is there any pattern to solve such kind of problem ?\n\n**Let\'s Discuss all of these questions**\n\n---\n* This is problem is almost similar to other subarray problem, where we find answer for smaller size subarray then using the answer of these smaller size problem we answer for bigger size problem.\n\n* But the new thing in this question is after bursting all **n-1**  balloons , for the last balloons there is no one in it\'s neighbour.\n* And to solve this problem we add two padded balloons at both end , so when last balloon burst then these padding balloons with acts neighbour for it. \n\nwe will genrate all subarray of len 1 to n  , this will we done by using gap strategy \n```\nwlen -  subarray window len\n\tfor(int wlen=1;wlen<=n;wlen++ ){\n\t\t\tfor(int left =  1;left<=n-wlen+1;left++){\n\t\t\t\t\tint right =  left+wlen-1;\n\t\t\t\t}\n\t\t\t}\n```\nThis is how we will genrate all subarray \n\n* Remeber That point again to answer larger size problem we need to use smaller size problem.\n* so if we fill dp for one size subarry,then we can answer for 2 size subarray and so on...\n                               (and for one size subarray single balloons with be last balloon.)\n* our dp[i][j] = maximum coins earn when bursting all balloons in that subarray\n* as dp[i][j] representing only max coin earn in i to j size subarray\n* **we need one equation to fill dp[i][j]** Suppose we burst kth index at last , we need answer for smaller size array which is already calculated\n```\nNow itertate subarray form left to right, kth index balloons will burst array \nk=left to k =  right\n\n dp[left][right]  = Math.max(dp[left][right],\n                             dp[left][k-1]+ // left subarray already calculated\n                             dp[k+1][right]+ // right subarray  already calculated\n                             (arr[k]*arr[left-1]*arr[right+1]) // last burst balloons\n```\n\n---\nComplete Code:\n\n---\n```\nclass Solution {\n    public int maxCoins(int[] nums) {\n        \n        int n =  nums.length;\n        int arr[] =  new int[n+2]; \n        for(int i=0;i<n;i++){\n            arr[i+1] = nums[i];\n        }\n        arr[0]=1;arr[n+1] =  1;\n        int dp[][]  = new int[n+2][n+2];\n        //  dp[i][j]  -  storing the max coins u can earn in  this interval/subarray\n        \n        for(int wlen=1;wlen<=n;wlen++ ){\n            for(int left =  1;left<=n-wlen+1;left++){\n                int right =  left+wlen-1;\n                \n                // now iterate this window, and give chance to every ballon to burst at last\n                for(int k=left;k<=right;k++){\n                    dp[left][right]  = Math.max(dp[left][right],\n                                               dp[left][k-1]+ // left subarray \n                                                dp[k+1][right]+ // right subarray\n                                                (arr[k]*arr[left-1]*arr[right+1]) // bursting k index ballon at last , and intervals side balloons will bust with last balloon \n                                               )        ;                                    \n                }                                                \n            }\n        }\n        \n         return dp[1][n]; // returning answer stored for orginal size problem\n        \n        \n        \n    }\n}\n```\n\n\n**Overall conclusion :**\n* Add padding balloons so we have neighbour balloons for last remaining balloons.\n* **given chance to every balloons to burst at last in subarray of len wlen**\n* and rest things same as dp , to answer larger problem we need answer of smaller problem store them to use later \n* More problem solved by gap strategy Longest increasing subsequnce , longes palindrom string\n\n\t\t\t\t\n\n
['Java']