[Python] 5 lines dp, explained
This is quite difficult problem! Let us consider dp[i][j] the maximum number of coins we can get, popping balls from i to j, not including i and j. Why it is en
This is quite difficult problem! Let us consider `dp[i][j]` the maximum number of coins we can get, popping balls from `i` to `j`, **not including** `i` and `j`. Why it is enough to keep these values? Let us look at the **last** popped balloon with number `k`. Then our balloons are separated into two groups: to the left of this balloon and the the right and we can write:\n \n`dp[i][j] = max(nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]) for k in (i+1,j)`, \n\nwhere `k` is the index of the last balloon burst in `(i, j)`. \n\n**Complexity**: time complexity is `O(n^3)` and space complexity is `O(n^2)`.\n\nYou can see that code is very short, but it is in my opinion very diffucult to find this solution. How you can think in problems like this? First of all we are given, that `n<500`, which is quite small and we can try to understand what complexity we can expect. It is for sure not `2^500`, so what is rest some polynomials and/or logarithms.  So what we can expect is either `O(n^2)` or `O(n^3)`, but no more than this. So at this moment we usually have `2` choises: either greedy or dp. It is not obvious how to do greedy for me, so the choise is dp. Now we can think that repeating subproblem is what is the answer on range `(i, j)`. However the last step is something you can not invent quickly if you do not have experience in these type of problems. I can give you only intuition here: it is good idea to look at some **extremal** characteristic here: by this word I mean some object, which is either first/last, biggest/smallest and so on. Here our characteristic is **last** popped ballon on range, not the **first** we expect in simpler dp problems. Once you understand this logic, some other problems similar to this will be slightly simpler.\n\n**664** Strange Printer\n**546** Remove Boxes\n**1000** Minimum Cost to Merge Stones\n\n```\nclass Solution:\n    def maxCoins(self, nums):\n        A = [1] + nums + [1]\n        \n        @lru_cache(None)\n        def dfs(i, j):\n            return max([A[i]*A[k]*A[j] + dfs(i,k) + dfs(k,j) for k in range(i+1, j)] or [0])\n        \n        return dfs(0, len(A) - 1)\n```\n\n#### Solution 2\nAfter leetcode added new tests, previous elegant approach not working anymore, so we need to do it in classical dp table. Complexity is the same, but it get AC now. Thanks **rowe1227** for providing the code.\n\n```python\nclass Solution:\n    def maxCoins(self, A):\n        A, n = [1] + A + [1], len(A) + 2\n        dp = [[0] * n for _ in range(n)]\n        \n        for i in range(n - 2, -1, -1):\n            for j in range(i + 2, n):\n                dp[i][j] = max(A[i]*A[k]*A[j] + dp[i][k] + dp[k][j] for k in range(i + 1, j))\n        \n        return dp[0][n-1]\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Dynamic Programming']