Java: Discussed both top down and bottom up approach
312. Burst Balloons\nApproach:\n A. BruteForce:\n  1. Generate all permutations of given array and consider each permutation to be the order of bursting balloon
**312. Burst Balloons**\n**Approach:**\n **A. BruteForce:**\n  1. Generate all permutations of given array and consider each permutation to be the order of bursting balloons\n  2. For each permutation, compute the cost and keep track of maximum cost\n  3. Return max cost\n \n  **Complexity**\n  1. **Time**: O(n!)\n       There will be n! permutations. Computing cost for each permutation would take O(n^2). so essentially total cost will\n       be O(n!)\n  2. **Space**: O(n)\n       Permutations can be made using recursion and we will need an array to hold one permutation.\n \n **B. Top Down Recursion with DP**\n  1. Suppose function f(start, end) gives max cost for bursting balloons in range of [start, end]\n  2. This function can be defined recursively as\n  3. ```\n       f(start, end) = maximum of (\n\t                     f(start, k - 1) +\n\t\t\t\t\t\t\tnums[start - 1] *  nums[k] * nums[end + 1]) +\n\t\t\t\t\t\t\tf(k + 1, end)\n\t\t\t\t\t\t\t) where k lies in range [start, end]\n\t   ```\n       Here,\n       **`f(start, k - 1):`** means total maximum cost from left sub array\n       **`nums[start - 1] * nums[k] * nums[end + 1]`**: Cost of bursting balloon k considering it is the last balloon bursted in\n       this group from [start, end]\n       **`f(k + 1, end)`**: means total maximum cost from right sub array\n\t   \n  **Complexity**\n  **1. Time: O(n^3)**\n       For filling each value in memo table, one loop is needed. Hence, to fill N^2 states, we need N^3 complexity\n  **2.Space: O(n^2)** for memo table\n \n ```\n     private static int computeTopDown(int[] nums) {\n        int n = nums.length;\n        int[] newNums = new int[n + 2];\n        System.arraycopy(nums, 0, newNums, 1, n);\n        newNums[0] = 1;\n        newNums[newNums.length - 1] = 1;\n\n        int[][] memo = new int[n + 2][n + 2];\n        compute(newNums, memo, 1, n);\n        return memo[1][n];\n    }\n\n    /**\n     * recursive top down approach\n     *\n     * @param nums:  input array\n     * @param memo:  memo table\n     * @param start: starting index of array\n     * @param end:   ending index of array\n     * @return\n     */\n    private static int compute(int[] nums, int[][] memo, int start, int end) {\n        if (start > end) {\n            return 0;\n        }\n        if (memo[start][end] != 0) {\n            return memo[start][end];\n        }\n        int maxValue = 0;\n        for (int mid = start; mid <= end; mid++) {\n            maxValue = Math.max(maxValue,\n                    // nums[start - 1] means the rightmost unburst balloon from the left subarray\n                    // nums[end + 1] means the leftmost unburst balloon from the right subarray\n                    // the above two balloons will be needed to compute cost while bursting mid balloon.\n                    nums[start - 1] * nums[mid] * nums[end + 1] +\n                            compute(nums, memo, start, mid - 1) +\n                            compute(nums, memo, mid + 1, end));\n        }\n        memo[start][end] = maxValue;\n        return maxValue;\n    }\n\n ```\n \n  **C. Bottom Up**\n  1. The above algorithm can be implemented in bottom up manner using nested loops\n  **Complexity**\n  **1. Time: O(N^3)** There are 3 loops\n  **2. Space: O(N^2)** : memo table\n  \n  ```\n      /**\n     * This is an iterating way for above approach.\n     *\n     * @param nums\n     * @return\n     */\n    private static int computeBottomUp(int[] nums) {\n        int n = nums.length;\n        int[] newNums = new int[n + 2];\n        System.arraycopy(nums, 0, newNums, 1, n);\n        newNums[0] = 1;\n        newNums[newNums.length - 1] = 1;\n        int[][] memo = new int[n + 2][n + 2];\n\n        for (int len = 1; len <= n; len++) {\n            for (int start = 0; start < n - len + 1; start++) {\n                int end = start + len + 1;\n                for (int mid = start + 1; mid < end; mid++) {\n                    // start and end will point to array element which are out of bounds for current subarray.\n                    // here since, mid is iterating from start + 1 to end - 1 hence, we will populate memo with those values\n                    // only.\n                    memo[start + 1][end - 1] = Math.max(memo[start + 1][end - 1],\n                            newNums[start] * newNums[mid] * newNums[end] +\n                                    memo[start + 1][mid - 1] +\n                                    memo[mid + 1][end - 1]);\n                }\n            }\n        }\n        return memo[1][n];\n    }\n  ```
['Dynamic Programming', 'Recursion', 'Java']