Simple Python DP solutions
Key point: reverse thinking. \nThink about n balloons if k is the last one to burst, last_burn = nums[-1] * nums[k] * nums[n]. \nWe can see that the balloons is
Key point: reverse thinking. \nThink about n balloons if k is the last one to burst, last_burn = nums[-1] * nums[k] * nums[n]. \nWe can see that the balloons is again separated into 2 sections. The left and right section \nnow has well defined boundary and do not affect each other! Therefore we can use dynamic algorithm.\n\nTime complexity: O(n^3) because of O(n^2) subproblem, O(n) for each subproblem\nSpace complexity: O(n^2)\n\nTop-down approach:\n```\n    def maxCoins(self, nums):\n        def recursive(i, j):\n            if i >= j - 1:\n                return 0\n            if (i, j) in dp:\n                return dp[(i, j)]\n            tmp = 0\n            for k in range(i + 1, j):\n                last_burn = nums[i] * nums[k] * nums[j]\n                tmp = max(tmp, recursive(i, k) + recursive(k, j) + last_burn)\n            dp[(i, j)] = tmp\n            return dp[(i, j)]\n        \n        nums = [1] + [x for x in nums if x > 0] + [1]\n        dp = {}\n        return recursive(0, len(nums) - 1)\n```\n\nBottom-up approach:\n```\n    def maxCoins(self, nums):\n        nums = [1] + [x for x in nums if x > 0] + [1]\n        n = len(nums)\n        dp = [[0] * n for _ in range(n)]\n        for d in range(2, n):\n            for i in range(0, n - d):\n                j = i + d\n                for k in range(i + 1, j):\n                    last_burn = nums[i] * nums[k] * nums[j]\n                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + last_burn)\n        return dp[0][n - 1]\n```
[]