Python3, complete thinking with explanation, O(n!) to O(n^3)
I. Brute-force: try every balloon on by one, then solve the sub problem recursively.\n>\npython\n    class Solution:\n        def maxCoins(self, nums) -> int:\n
> **I. Brute-force:** try every balloon on by one, then solve the sub problem recursively.\n>\n```python\n    class Solution:\n        def maxCoins(self, nums) -> int:\n            k, dp = "1"*len(nums), {}\n            nis = [(i,c) for i, c in enumerate(nums)]\n\n            def _max(sub_nis, k, dp):\n                if not sub_nis:\n                    return 0\n                if k in dp:\n                    return dp[k]\n                x = 0\n                for i in range(len(sub_nis)):\n                    left, it, right = _coin(sub_nis, i-1), _coin(sub_nis, i), _coin(sub_nis, i+1)\n                    sub = sub_nis[:i] + sub_nis[i+1:]\n                    x = max(x, left[1]*it[1]*right[1]+_max(sub, k[:it[0]]+"0"+k[it[0]+1:], dp))\n                dp[k] = x\n                return x\n\n            def _coin(nis, i):\n                if i < 0 or i >= len(nis):\n                    return (-1, 1)\n                return nis[i]\n\n            x = _max(nis, k, dp)\n            return x\n```\n>\n> recursive expresion of this brutal idea is:  \n\n![image](https://assets.leetcode.com/users/pizzacrystal/image_1569314831.png)\n\n> easy to figure out its time complexity is $O(n!)$, hereby it no doubt exceeds time limitation.  \n\n> **II. Optimized Brute-force:** omits array slices by delaying calculation until getting valid $X_{right}$.\n>\n```python\n    class Solution:\n        def maxCoins(self, nums) -> int:\n            if not nums:\n                return 0\n            k, dp = "1"*len(nums), {}\n\n            def _burst(nums, k, dp):\n                if k in dp:\n                    return dp[k]\n                l2left, left, _max, _len, j = None, 1, 0, len(nums), -1\n                for i in range(_len):\n                    if k[i] == \'0\':\n                        continue\n                    if l2left is not None:\n                        _max = max(_max, l2left*left*nums[i]+_burst(nums, k[:j]+"0"+k[j+1:], dp))\n                    l2left, left, j = left, nums[i], i\n                else:\n                    if j != -1:\n                        _max = max(_max, l2left*left+_burst(nums, k[:j]+"0"+k[j+1:], dp))\n                dp[k] = _max\n                return _max\n\n            x = _burst(nums, k, dp)\n            return x\n```\n>\n> time complexity is still $O(n!)$, though this implementation has higher performance.  \n\n> **III. DP (top down):** thinking of selecting the first balloon is inevitably TLE, which prompts us to address it in another way -- consider the case of picking the last one. if we knew $X$ should be picked in the end, we get the transition equation as below:  \n\n![image](https://assets.leetcode.com/users/pizzacrystal/image_1569314893.png)\n\n> apparently, we need to examine every $X$ in $A$, but it is remarkably faster than brute-force method because of "devide and conquer". As for memoization, we could use a 2-D array $dp[i][j]$ to cache results of left and right sub arrays. Here is the implementation:  \n>\n```python\n    class Solution:\n        def maxCoins(self, nums) -> int:\n            if not nums:\n                return 0\n            _len = len(nums)\n            dp = [[-1]*_len for _ in range(_len)]\n\n            def _burst(left, right, b, e):\n                if e < b:\n                    return 0\n                if dp[b][e] != -1:\n                    return dp[b][e]\n                _max = 0\n                if b == e:\n                    dp[b][e] = left * nums[b] * right\n                else:\n                    for i in range(b, e+1):\n                        last = left * nums[i] * right\n                        lhalf = _burst(left, nums[i], b, i-1)\n                        rhalf = _burst(nums[i], right, i+1, e)\n                        _max = max(_max, last+lhalf+rhalf)\n                    dp[b][e] = _max\n                return dp[b][e]\n\n            return _burst(1, 1, 0, _len-1)\n```\n>\n> recursion tree is in need to analyse time complexity, omitted here.  \n\n> **IV. DP (bottom up):** By translating recursion cycles to for-loops, we get the final solution.\n>\n```python\n    class Solution:\n        def maxCoins(self, nums) -> int:\n            if not nums:\n                return 0\n            nums = [1] + nums + [1]\n            _len = len(nums)\n            dp = [[0]*_len for _ in range(_len)]\n\n            for l in range(1, _len+1):\n                for i in range(1, _len-l):\n                    j = i + l - 1\n                    for k in range(i, j+1):\n                        dp[i][j] = max(dp[i][j], nums[i-1]*nums[k]*nums[j+1]+dp[i][k-1]+dp[k+1][j])\n            return dp[1][_len-2]\n```\n>\n> the inner loop calculates coins of specific array, while the outer two loops examine all sub arrays that are of length $1$ to length $n$, thereby we get correct result finally. Time complexity is $O(n^3)$, which is overwhelming compared to $O(n!)$.\n
[]