Java DP solution with detailed explanation, O(n^3)
This solution is inspired by The_Duck with his C++ solution\n\nhttps://leetcode.com/discuss/72186/c-dynamic-programming-o-n-3-1100-ms-with-comments\n\nHowever, 
This solution is inspired by The_Duck with his C++ solution\n\nhttps://leetcode.com/discuss/72186/c-dynamic-programming-o-n-3-1100-ms-with-comments\n\nHowever, I would give an explanation based on my own understanding. \n\nThe basic idea is that we can find the maximal coins of a subrange by trying every possible final burst within that range. Final burst means that we should burst balloon i as the very last one and burst all the other balloons in whatever order. dp[i][j] means the maximal coins for range [i...j]. In this case, our final answer is dp[0][nums.length - 1]. \n\nWhen finding the maximal coins within a range [start...end], since balloon i is the last one to burst, we know that in previous steps we have already got maximal coins of range[start .. i - 1] and range[i + 1 .. start], and the last step is to burst ballon i and get the product of balloon to the left of i, balloon i, and ballon to the right of i. In this case, balloon to the left/right of i is balloon start - 1 and balloon end + 1. Why? Why not choosing other balloon in range [0...start - 1] and [end + 1...length] because the maximal coins may need other balloon as final burst?\n\nIn my opinion, it's because this subrange will only be used by a larger range when it's trying for every possible final burst. It will be like [larger start.....start - 1, [start .. end] end + 1/ larger end], when final burst is at index start - 1, the result of this sub range will be used, and at this moment, start - 1 will be there because it's the final burst and end + 1 will also be there because is out of range. Then we can guarantee start - 1 and end + 1 will be there as adjacent balloons of balloon i for coins. That's the answer for the question in previous paragraph.\n\n\n    public class Solution {\n    public int maxCoins(int[] nums) {\n        if (nums == null || nums.length == 0) return 0;\n        \n        int[][] dp = new int[nums.length][nums.length];\n        for (int len = 1; len <= nums.length; len++) {\n            for (int start = 0; start <= nums.length - len; start++) {\n                int end = start + len - 1;\n                for (int i = start; i <= end; i++) {\n                    int coins = nums[i] * getValue(nums, start - 1) * getValue(nums, end + 1);\n                    coins += i != start ? dp[start][i - 1] : 0; // If not first one, we can add subrange on its left.\n                    coins += i != end ? dp[i + 1][end] : 0; // If not last one, we can add subrange on its right\n                    dp[start][end] = Math.max(dp[start][end], coins);\n                }\n            }\n        }\n        return dp[0][nums.length - 1];\n    }\n    \n    private int getValue(int[] nums, int i) { // Deal with num[-1] and num[num.length]\n        if (i < 0 || i >= nums.length) {\n            return 1;\n        }\n        return nums[i];\n    }\n}
['Dynamic Programming', 'Java']