Python, dynamic programming solution with explanation
based on scoring rule, the score of bursting nums[i] is nums[i - 1] * nums[i] * nums[i + 1], and i - 1 or i + 1 goes out of bounds of the array, treat it as if 
based on scoring rule, the score of bursting ```nums[i]``` is ```nums[i - 1]``` * ```nums[i]``` * ```nums[i + 1]```, and ```i - 1``` or ```i + 1``` goes out of bounds of the array, treat it as if there is a balloon with a ```1``` painted on it.\nSo, add ```1``` at the first and the end of ```nums```\n```dp[i][j]``` means how much score we can get from ```nums[i+1:j]``` ->  ```(i, j)``` open interval.\n\n```k``` is the balloon we is to burst **last** in the open interval ```(i, j)```, we can calculate score after burst every balloons in the open interval ```(i, j)```, and find the max score.\n```dp[i][k]``` is the max score we can from open interval ```(i, k)```, ```dp[k][j]``` is the max score we can from open interval ```(k, j)```,\n```dp[i][k]``` means the balloons in the closed interval ```[i+1, k-1]``` have been bursted, ```dp[k][j]``` is the same.\nso ```dp[i][j]``` is ```max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j] for k in closed interval [i+1, j-1])```\n\neg. nums=```[3,1,5,8]```\n<img src="https://latex.codecogs.com/svg.image?\\begin{bmatrix}&space;&&space;1&space;&&space;3&space;&&space;1&space;&&space;5&space;&&space;8&space;&&space;1&space;\\\\1&space;&&space;0&space;&&space;0&space;&&space;3&space;&&space;30&space;&&space;159&space;&&space;167&space;\\\\3&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;15&space;&&space;135&space;&&space;159&space;\\\\1&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;40&space;&&space;48&space;\\\\5&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;40&space;\\\\8&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;\\\\1&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;\\end{bmatrix}" />\n\n### iteration\ndp array is filled from bottom to top, from left to right\ntc is```O(len(nums)**3)```, sc is ```O(0.5*len(nums)**2)```\n```\nclass Solution:\n    def maxCoins(self, nums: List[int]) -> int:\n        if len(nums) == 1: return nums[0]\n        nums = [1] + nums + [1]\n        leng = len(nums)\n        dp = [[0] * leng for _ in range(leng)]\n        for i in range(leng-2,-1,-1):\n            for j in range(i, leng):\n                for k in range(i+1, j):\n                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i]*nums[j]*nums[k])\n        return dp[0][leng-1]\n```\n\n### dfs\ntc is```O(len(nums)**3)```, sc is ```O(0.5*len(nums)**2)```\n```\nclass Solution:\n    def maxCoins(self, nums: List[int]) -> int:\n        if len(nums) == 1: return nums[0]\n        nums = [1] + nums + [1]\n        leng = len(nums)\n        @cache\n        def dfs(i, j):\n            if j - i <= 1: return 0 # there is no balloon between the neighbor\n            ans = 0\n            for k in range(i+1, j):\n                ans = max(ans, dfs(i,k) + dfs(k,j) + nums[i] * nums[j] * nums[k])\n            return  ans\n        return dfs(0, leng-1)\n```
['Dynamic Programming', 'Python']