[Java] Dynamic Programming
Idea\n1. What makes this problem difficult to solve is, when we have a lot of balloons, we are not sure what the neighbor balloon is. So, thinking in terms of w
### Idea\n1. What makes this problem difficult to solve is, when we have a lot of balloons, we are not sure what the neighbor balloon is. So, thinking in terms of what the first balloon to pop is not straight-forward.\n2. Let\'s consider in terms of what the last balloon to pop in a given range is. Given `[A, B, C, D, E]` balloons, let\'s consider we pop `[B, C, D]` first.  `[A, *B, *C, *D, E]`. Among these three balloons, what happens if we decide to pop `C` last? We will get points from popping the other two, and then we will get points of the product of `A` * `C` *  `E` (the other two edges).\n3. Saying it generally, if we decide to pop `i`th balloon last between range `a` and `b`, the max point would be\n`[nums[0], ..., nums[a - 1], nums[a], ..., nums[i], ...nums[b], nums[b + 1], ... nums[n - 1]]`, the max point would be:\n`maxpoint from popping balloon a to i - 1` + `nums[a - 1] * nums[i] * nums[b + 1]` + `maxpoint from popping ballon i + 1 to balloon b`.\n4. Since we don\'t know what `i` value is, we iterate through all the possible `i`. In the code sample, the `i` value is named as `last`\n5. Given this, the shorter range should be computed before the longer range. That is, to know the max point we can get from range `0 to 5`, we should know what the max point we can get from `0 to 4` because the said `i` could be `5`.\n\n### Implementation details\n1. It is much easier to implement the dp when we have the dummy end points. So, I constructed a new array with `1` on each end.\n2. To make it obvious, what the left and right end points we are considering, I named the left-most balloon index `left`, and the right-most balloon index `right`.\n3. To prevent repeated computations, I used the memoization. The repeated query is, given `left` and `right` end point what the max `dp` is. So, it is a 2-dimensional `dp`.\n4. When the `len` is 1, do we need special handling? The code we wrote (`maxValue = Math.max(balloons[last] * balloons[left - 1] * balloons[right + 1] + dp[left][last - 1] + dp[last + 1][right], maxValue);`)is fine, because `dp[left][last - 1]` and `dp[last + 1][right]` are both initialized as `0` in Java.\n\n### Sample Code\n``` java\nclass Solution {\n    public int maxCoins(int[] nums) {\n        int n = nums.length + 2;\n        int[] balloons = buildBalloonArray(nums);  // see implementation detail # 1\n        int[][] dp = new int[n][n]; // see implementation detail # 3\n        for (int len = 1; len <= n - 2; len++) { // see idea # 5\n            for (int left = 1; left < n - 1; left++) { // see implementation detail # 2\n                int right = left + len - 1; // see implementation detail # 2\n                if (right >= n - 1) {\n                    break;\n                }\n                int maxValue = 0;\n                for (int last = left; last <= right; last++) { // see idea # 4\n                    maxValue = Math.max(balloons[last] * balloons[left - 1] * balloons[right + 1] \n                                        + dp[left][last - 1] + dp[last + 1][right], maxValue); // see idea # 3, implementation detail # 4\n                }\n                dp[left][right] = maxValue;\n            }\n        }\n        return dp[1][n - 2];\n    }\n    \n    private int[] buildBalloonArray(int[] nums) {\n        int n = nums.length;\n        int[] balloons = new int[n + 2];\n        for (int i = 0; i < n; i++) {\n            balloons[i + 1] = nums[i];\n        }\n        balloons[0] = 1;\n        balloons[n + 1] = 1;\n        return balloons;\n    }\n}\n```\n\nPlease let me know if you have any questions, and upvote it if you liked it.
['Dynamic Programming', 'Java']