[Java] Top Down and Bottom Up Approach, O(N^3) time and O(N^2) space
Top Down Approach: O(N^3) Time and O(N^2) Space due to DP Array and stack space of recursion\n\nclass Solution {\n    public int maxCoins(int[] nums) {\n       
**Top Down Approach: O(N^3) Time and O(N^2) Space due to DP Array and stack space of recursion**\n```\nclass Solution {\n    public int maxCoins(int[] nums) {\n        //TopDown Approach\n        int[][] dp = new int[nums.length][nums.length];\n        for(int i = 0; i < nums.length; i++)Arrays.fill(dp[i], -1);\n        \n        return maxCoinsTopDown(nums, 0, nums.length - 1, dp);\n    }\n    public int maxCoinsTopDown(int[] nums, int leftIdx, int rightIdx, int[][] dp){\n        //base case\n        if(leftIdx > rightIdx)return 0;\n        if(dp[leftIdx][rightIdx] != -1)return dp[leftIdx][rightIdx];\n        \n        int leftBoundary = leftIdx != 0? nums[leftIdx - 1]: 1;\n        int rightBoundary = rightIdx != nums.length - 1? nums[rightIdx + 1]: 1;\n        \n        if(leftIdx == rightIdx)return dp[leftIdx][rightIdx] = leftBoundary * nums[leftIdx] * rightBoundary;\n        \n        int maxCoins = 0;\n        for(int lastBalloonIdx = leftIdx; lastBalloonIdx <= rightIdx; lastBalloonIdx++){\n            \n            //picking the balloon at lastBalloonIdx to be the last balloon to be burst\n            //among the balloons in the range leftIdx to rightIdx\n            \n            maxCoins = Math.max(maxCoins, leftBoundary * nums[lastBalloonIdx] * rightBoundary + \n                               maxCoinsTopDown(nums, leftIdx, lastBalloonIdx - 1, dp) + \n                               maxCoinsTopDown(nums, lastBalloonIdx + 1, rightIdx, dp));\n        }\n        return dp[leftIdx][rightIdx] = maxCoins;\n    }\n}\n```\n\n**Bottom Up Approach: O(N^3) time and O(N^2) space due to DP Array**\n```\nclass Solution {\n    public int maxCoins(int[] nums) {\n        //bottomUp Approach\n        int[][] dp = new int[nums.length][nums.length];\n        \n        for(int len = 1; len <= nums.length; len++){\n            for(int i = 0; i < nums.length + 1 - len; i++){\n                \n                int leftBoundary = (i != 0)? nums[i - 1]: 1;\n                int rightBoundary = (i + len < nums.length)? nums[i + len]: 1;\n                \n                int k = i + len - 1;\n                for(int j = i; j <= k; j++){\n                    //in the range of balloons from i to k, picking the balloon at jth\n                    //idx to be the last balloon to burst\n                    dp[i][k] = Math.max(dp[i][k],\n                                        leftBoundary * nums[j] * rightBoundary + \n                                        (j > 0? dp[i][j - 1]: 0) + \n                                        (j < nums.length - 1? dp[j + 1][k]: 0));\n                }\n            }\n        }\n        return dp[0][nums.length - 1];\n    }\n}\n```
[]