python solutions with visualized explanations
Refer to the example of balloons [3,1,5,8] where n=4. Append a balloon painted with 1 in the head (nums[-1] = 1), and a balloon painted with 1 in the tail (nums
1. Refer to the example of balloons `[3,1,5,8]` where `n=4`. Append a balloon painted with `1` in the head (`nums[-1] = 1`), and a balloon painted with `1` in the tail (`nums[n] = 1`):\n\n   ### \uD83C\uDF88  \uD83C\uDF88  \uD83C\uDF88  \uD83C\uDF88  \uD83C\uDF88  \uD83C\uDF88\n\n     1    &nbsp;&nbsp;&nbsp; 3&nbsp;&nbsp;&nbsp;     1&nbsp;&nbsp;&nbsp;     5&nbsp;&nbsp;&nbsp;     8&nbsp;&nbsp;&nbsp;    1\n\n   Now we have `n=6` balloons in total, starting from index `0` to index `5`.\n\n2. Define `dp` as an `n * n `(or `6 * 6`) matrix, where `dp[i][j]` is the maximum coins we can collect by bursting balloons from index `i` to index `j`. For example, `dp[3][3]=5`,`dp[0][1]=3`. Note that the balloon `0` and `5` can never be bursted for coins.\n\n   Now the question has been reduced to how to compute `dp[1][4]` for the maximum coins we can collect by bursting balloons from index `1` to index `4`.\n\n3. Assume the **last** balloon we burst is `k (i <= k <= j)`. We have the following transition function:\n\n   ```python\n   left = nums[i-1]\n   right = nums[j+1]\n   dp[i][j] = dp[i, k-1] + left * nums[k] * right + dp[k+1, j]\n   ```\n\n   For example, suppose `i=1, j=4, k=3`. We burst from index `1` to index `2` for the coins of`dp[i, k-1]`:\n\n   ### \uD83C\uDF88  \u2716\uFE0F  \u2716\uFE0F  \uD83C\uDF88  \uD83C\uDF88  \uD83C\uDF88\n\n     1    &nbsp;&nbsp;&nbsp; 3&nbsp;&nbsp;&nbsp;     1&nbsp;&nbsp;&nbsp;     5&nbsp;&nbsp;&nbsp;     8&nbsp;&nbsp;&nbsp;    1\n\n   And subsequently we burst from index `4` to index `4` for the coins of `dp[k+1, j]`:\n\n   ### \uD83C\uDF88  \u2716\uFE0F  \u2716\uFE0F  \uD83C\uDF88  \u2716\uFE0F  \uD83C\uDF88\n\n     1    &nbsp;&nbsp;&nbsp; 3&nbsp;&nbsp;&nbsp;     1&nbsp;&nbsp;&nbsp;     5&nbsp;&nbsp;&nbsp;     8&nbsp;&nbsp;&nbsp;    1\n\n   **At last** we burst the balloon of index `k=3`, whose left balloon is of index `i-1=0`, and the right balloon is of index `j+1=5`. The coins for this burst is `nums[i-1]*nums[k]*nums[j+1]`:\n\n   ### \uD83C\uDF88  \u2716\uFE0F  \u2716\uFE0F  \u2716\uFE0F  \u2716\uFE0F  \uD83C\uDF88\n\n     1    &nbsp;&nbsp;&nbsp; 3&nbsp;&nbsp;&nbsp;     1&nbsp;&nbsp;&nbsp;     5&nbsp;&nbsp;&nbsp;     8&nbsp;&nbsp;&nbsp;    1\n\n4. How many possible positions for `k` when computing `dp[i][j]`? We loop through `i` to `j`, and there are `(j+1-i)` positions, or `(j+1-i)` possible ways to earn coins. We look for the way to collect the maximum coins.\n\n   ```python\n   coins_max = 0\n   for k in range(i, j + 1):\n     left = nums[i-1]\n     right = nums[j+1]\n     coins_k_max = cal(i, k - 1) + left * nums[k] * right + cal(k + 1, j)\n     coins_max = max(coins_max, coins_k_max)\n   ```\n\nCodes:\n```python\nclass Solution:\n    def maxCoins(self, nums: List[int]) -> int:\n        # Append a balloon painted with `1` in the head, and a balloon painted with `1` in the tail:\n        nums = [1] + nums + [1]\n        # current balloons (with two `vitural` ballons)\n        n = len(nums)\n        # dp[i][j]: the maximum coins we can collect by bursting balloons from index `i` to index `j`\n        dp = [[0 for _ in range(n)] for _ in range(n)]\n\n        # compute dp[i][j]\n        def cal(i, j):\n            # memory\n            if dp[i][j]:\n                return dp[i][j]\n            # Meaningless case. Just return 0. \n            elif i > j:\n                return dp[i][j]\n            else:\n                coins_max = 0\n                # loop through (j+1-i) possible positions for the last balloon\n                for k in range(i, j + 1):\n                    left = nums[i-1]\n                    right = nums[j+1]\n                    coins_k_max = cal(i, k - 1) + left * nums[k] * right + cal(k + 1, j)\n                    coins_max = max(coins_max, coins_k_max)\n                # update the memory\n                dp[i][j] = coins_max\n                return dp[i][j]\n        # compute dp[1][n-2]\n        return cal(1, n - 2)\n\t
[]