JAVA | DP | Divide and Conquer | Sliding Window | Detailed Explanation Using Image
Intution: Suppose you have been given array [1,2,3,4] which u can see as [1,1,2,3,4,1] (padded by 1 on both side). So now if u decide to burst baloon with value
**Intution:** Suppose you have been given array [1,2,3,4] which u can see as [1,1,2,3,4,1] (padded by 1 on both side). So now if u decide to burst baloon with value 3 at last then that means all other baloons will already burst and so total value to burst the baloons will be = (1 * 3 * 1 + left + right) where left will be max cost of bursting baloons left to 3 i.e., [1,2] and right will be max cost of bursting baloons t the right of 3 i.e., [4].\nSo here we can clearly observe that to get the answer for window of size n we need to have the answer for window of size 2(left) and 1(right) that is smaller subproblems. So here we can definitely think of DP.(Divide and Conquer DP)\n\n**Explanation of Approach:**\n* Since we need smaller window answer for larger windows, so we have to store the answer for window of each size from 1 to n.\n* Then we will have two pointers left and right to point at the two ends of our current window. For example if we have array [1,1,2,3,4,5,1] and we have to get the answer for subarray [2,3,4] then left will point at index 2and right at index 4.\n* Now in the current window we have to burst baloons in such sequence that we get the max value. And for this we have to check for each baloon in that window whether it can give the max value if burst at last.\n* So for this we have to traverse from left to right in the window and each time calculate the value assuming ith baloon is burst at last.\n* So while filling Dp we will be filling values for left to right window , i.e., \n\tdp[left][right] = Max(already calculated value, burst this ith baloon last and add left and right subarray points within the window)\n* dp[left][right] = max(dp[left][right], arr[left-1] * arr[i] * arr[right+1] + dp[left][i-1] + dp[i+1][right])\n\n![image](https://assets.leetcode.com/users/images/f4759f64-98cb-4493-9ed7-5a50251cdfc1_1641000994.937502.jpeg)\n\nSo now we just need to apply 3 loops:\n1. 1st for window size from 1 to n\n2.  then for left pointer from 1 to (n-window+1)\n3.  Now right is already fixed i.e., (left+window-1), so now third loop from left to right.\nEach time update the value in dp for left to right.\n4. Time Complexity : O(N^3)\n\n\n\u274C**Approach 0: Recursion (Here we will only understand why to not do using recusrion)**\n\n**For that Lets first see the power of DP over recursion:**\nif we do it by recusrion then we have to make N! calls to cover all the permutations of N sized array and then to calculate points for each permutation we need O(N). So by recursion Time Complexity will be O(N!N)\nSo now if N=20,\nthen N! = 2.43 * 10^18 => N!N = 4.86 * 10^19\nand if we assume we can do 10^8 computations in 1sec then the above value of N!N gonaa take approx 3168 years to compute!! LOL!!\n\nAnd at the same time for DP the Time Complexity is N^3 = 8000 < 1sec\n##### From 3168 years to less than 1sec => I think this is more than enough to understand the power of DP.\n\n\n**Approach1 : Memoization**\n```\nclass Solution {\n    public int maxCoins(int[] nums) {\n        int n = nums.length;\n        int arr[] = new int[n+2];\n        arr[0] = arr[n+1] = 1;\n        for(int i=1;i<=n;i++){\n            arr[i] = nums[i-1];\n        }\n        \n        int memo[][] = new int[n+2][n+2];\n        return burst(memo, arr, 0, n + 1);\n        \n    }\n    public int burst(int[][] memo, int[] nums, int left, int right) {\n        if (left + 1 == right) return 0;\n        \n        if (memo[left][right] > 0) return memo[left][right];\n        \n        int ans = 0;\n        \n        for (int i = left + 1; i < right; ++i){\n            ans = Math.max(ans, nums[left] * nums[i] * nums[right] \n            + burst(memo, nums, left, i) + burst(memo, nums, i, right));\n        }\n        memo[left][right] = ans;\n        \n        return ans;\n    }\n    \n}\n```\n\n**Approach2 : DP**\n\n```\nclass Solution {\n    public int maxCoins(int[] nums) {\n        int n = nums.length;\n        int arr[] = new int[n+2];\n        arr[0] = arr[n+1] = 1;   // Giving padding of 1 to the corner elements\n        for(int i=1;i<=n;i++){\n            arr[i] = nums[i-1];   //final padded array\n        }\n        \n        int dp[][] = new int[n+2][n+2];\n        \n        for(int window = 1;window<=n;window++){     // window size\n\t\t\n            for(int left = 1;left<=n-window+1;left++){    // left pointer\n\t\t\t\n                int right = left+window-1;               // right pointer\n\t\t\t\t\n                for(int i=left;i<=right;i++){           // iterate from left to right\n\t\t\t\t\n                    dp[left][right] = Math.max(dp[left][right], (arr[left-1]*arr[i]*arr[right+1]) + dp[left][i-1] + dp[i+1][right]);\n                                    \n                }\n            }\n        }\n        return dp[1][n];\n    }\n}\n```\n\n**I hope it helps u....and wishing everyone an awsome and joyful New Year!!**
['Divide and Conquer', 'Dynamic Programming', 'Sliding Window', 'Java']