java 6ms dp solution with detailed explanation
This problem can be solved via divider conquer and dynamic programming. We use sum[i][j] to denote the max coins we can get for ballons from index i to index j.
This problem can be solved via divider conquer and dynamic programming. We use ```sum[i][j]``` to denote the max coins we can get for ballons from index ```i``` to index ```j```. \n\nHow can we calculate ```sum[i][j]```? Imagine kth (i <= k <= j) ballon is **the last one** we burst in the subarray [i, j]. Then the coin we can get for bursting kth ballon is apparently ```nums[i - 1] * nums[k] * nums[j + 1]```. And the total coins for [i, j] is ```sum[i][k - 1] + sum[k + 1][j] + nums[i - 1] * nums[k] * nums[j + 1]```. What we need to do is traverse from i to j to get the best **k**.\n\nNote that we add two dummy ballons to the head and tail respectively for the convenience of calculation.\n\n```\npublic int maxCoins(int[] nums) {\n\t// add dummy head and tail\n    int helpNum[] = new int[nums.length + 2]; \n    for(int i = 1; i <= nums.length; i++)\n        helpNum[i] = nums[i - 1];\n    helpNum[0] = 1;\n    helpNum[nums.length + 1] = 1;\n\t\n    int sum[][] = new int[helpNum.length][helpNum.length];\n    for(int gap = 0; gap < nums.length; gap++) {\n        for(int begin = 1; begin < nums.length - gap + 1; begin++) { // we don\'t consider the dummy head and tail\n            int end = begin + gap;\n            sum[begin][end] = Integer.MIN_VALUE;\n            int left = helpNum[begin - 1];\n            int right = helpNum[end + 1];\n\t\t\t\n\t\t\t// head and tail for current subrange need to be special processed\n            sum[begin][end] = Math.max(sum[begin][end], sum[begin + 1][end] + helpNum[begin] * left * right);\n            sum[begin][end] = Math.max(sum[begin][end], sum[begin][end - 1] + helpNum[end] * left * right);\n\t\t\t\n            for(int j = begin + 1; j < end; j++)\n                sum[begin][end] = Math.max(sum[begin][end], sum[begin][j - 1] + sum[j + 1][end] + helpNum[j] * left * right);\n        }\n    }\n    return sum[1][nums.length];\n}\n```
['Divide and Conquer', 'Dynamic Programming', 'Java']