PYTHON BEGINNER | Brute force recursion -> Brute-Better Memoization -> DP
dp[left][right] =  coins obtained from bursting all the balloons between left and right (not including left or right)\n dp[left][right] = max(nums[left] * nums[
* dp[left][right] =  coins obtained from bursting all the balloons between left and right (not including left or right)\n* dp[left][right] = max(nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]) for i in (left+1,right)\n\n* If i is the index of the last balloon burst in (left, right), the coins that burst will get are nums[left] * nums[i] * nums[right], and to calculate dp[left][right], we also need to add the coins obtained from bursting balloons between left and i, and between i and right, i.e., dp[left][i] and dp[i][right]\n\n```\n# Brute force recursion\nclass Solution:\n    def maxCoins(self, nums: List[int]) -> int:\n        nums = [1] + nums + [1]\n        return self.recurse(nums, 0, len(nums)-1)\n    \n    def recurse(self, nums, left, right):\n        \n        res = 0\n        for i in range(left+1, right):\n            coins = nums[left] * nums[i] * nums[right]\n            leftRes = self.recurse(nums, left, i)\n            rightRes = self.recurse(nums, i, right)\n            res = max(res, coins + leftRes + rightRes)\n        \n        return res\n\n    \n# Brute Better Memoization (69/70 Passed)\nclass Solution:\n    def maxCoins(self, nums: List[int]) -> int:\n        nums = [1] + nums + [1]\n        self.dp = [[-1 for _ in range(len(nums))] for _ in range(len(nums))]\n        return self.recurse(nums, 0, len(nums)-1)\n    \n    def recurse(self, nums, left, right):\n        \n        if self.dp[left][right] != -1:\n            return self.dp[left][right]\n        \n        res = 0\n        for i in range(left+1, right):\n            coins = nums[left] * nums[i] * nums[right]\n            leftRes = self.recurse(nums, left, i)\n            rightRes = self.recurse(nums, i, right)\n            res = max(res, coins + leftRes + rightRes)\n        \n        self.dp[left][right] = res\n        return res\n\n    \n# Top down DP (Accepted)\nclass Solution:\n    def maxCoins(self, nums: List[int]) -> int:\n        nums = [1] + nums + [1]\n        dp = [[0 for _ in range(len(nums))] for _ in range(len(nums))]\n        \n        for gap in range(len(nums)):\n            for left in range(len(nums)-gap):\n                right = left + gap\n                \n                res = 0\n                for i in range(left+1, right):\n                    coins = nums[left] * nums[i] * nums[right]\n                    res = max(res, coins + dp[left][i] + dp[i][right])\n                dp[left][right] = res\n                \n        return dp[0][len(nums)-1]\n```\n
['Dynamic Programming', 'Recursion', 'Memoization', 'Python', 'Python3']