[Python] Top Down DP
\n\nApproach: (click to show)\n\nThe idea here is to work backwards.\nDon\'t pop balloons **insert** balloons.\n\nWhile inserting balloons we need to keep track
<details>\n\n<summary><b>Approach:</b> (click to show)</summary>\n\nThe idea here is to work backwards.\nDon\'t pop balloons **insert** balloons.\n\nWhile inserting balloons we need to keep track of a few things.\n```left``` and ```right``` are the values of the last balloon inserted\nto the left and right of the current range.\n\n```i``` and ```j``` are the start and end indices of the current range.\n\nInitially we have the range [0, len(nums) - 1] and left = right = 1\nbecause no balloons have been inserted yet.\n\nThen when we insert a balloon with a value of 3 at index 5. \nWe now have two ranges to consider. \nThe first range is [0, 4] where left equals 1 but **right now**\n**equals 3** because we inserted a balloon with a \nvalue of 3.\n\nThe second range is [6, len(nums) - 1] where **left equals 3**\nand right equals 1.\n\nEvery time we insert a balloon we create two new ranges\n**until** the length of the range is 1 and we only have\none balloon to pick from to insert.\n\nEvery time a balloon is inserted add left * nums[k] * right\nto the total (where nums[k] is the value of the balloon inserted\nat index k).\n\nFor each sub-problem, consider all of the possible indices\nk where the balloon could be inserted and pick the one\nthat yields the maximum points.\n\n</details>\n\n<br>\n\n```python\ndef maxCoins(self, nums: List[int]) -> int:\n\n\t@functools.lru_cache(None)\n\tdef helper(left, right, i, j):\n\t\tif i >= j:\n\t\t\treturn left * right * nums[i] if i == j else 0\n\t\tbest = 0\n\t\tfor k in range(i, j+1):\n\t\t\tbest = max(best, left * nums[k] * right + helper(left, nums[k], i, k-1) + helper(nums[k], right, k+1, j))\n\t\treturn best\n\t\t\n\treturn helper(1, 1, 0, len(nums) - 1)\n```
[]