Python dp solutions: two implementation to help you understand
I understand how to solve the problem by reading the most 2 upvoted post.\nI write two diffenrent code to make sure I got the idea.\nThe only difference is the 
I understand how to solve the problem by reading the most 2 upvoted post.\nI write two diffenrent code to make sure I got the idea.\nThe only difference is the defination of the dp[i][j]\n```python\n    # dp[i][j] means the maximum coins we get after we burst all the balloons between i and j in the original array.\n    # between i and j means not include i and j, which means j-i >= 2 (let gap = j-i >=2)\n    # DP: dp[i][j] = max(nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j])(k in (i,j)]   Note: i<k<j\n    def maxCoins(self, nums: List[int]) -> int:\n        nums = [1] + nums + [1]\n        dp = [[0]*len(nums) for i in range(len(nums))]\n        \n        for gap in range(2,len(nums)):\n            for i in range(0,len(nums)-gap):\n                j = i+gap\n                for k in range(i+1,j):\n                    dp[i][j] = max(dp[i][j],nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j])\n                    \n        return dp[0][len(nums)-1]\n\t\t\n\t# Another implementation\t\n\tdef maxCoins(self, nums: List[int]) -> int:\n        nums = [1] + nums + [1]\n        dp = [[0]*len(nums) for i in range(len(nums))]\n\t\t\n        for i in range(len(nums)-1,-1,-1):\n            for j in range(i+2,len(nums)):\n                for k in range(i+1,j):\n                    dp[i][j] = max(dp[i][j],nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j])\n        \n        return dp[0][len(nums)-1]\n\n```\n\n```python\n    # dp[i][j] means the maximum coins we get after we burst all the balloons between i and j in the original array.\n    # between i and j means include i and j, j-i >=0  (let gap = j-i >=0)\n\t# DP: dp[i][j] = max(nums[i-1]*nums[k]*nums[j+1] + dp[i][k-1] + dp[k+1][j])(k in [i,j])  Note: i<=k<=j\n    def maxCoins(self, nums: List[int]) -> int:\n        nums = [1] + nums + [1]\n        dp = [[0]*len(nums) for i in range(len(nums))]\n        \n        for gap in range(0,len(nums)-2):\n            for i in range(1,len(nums)-1-gap):\n                j = i+gap\n                for k in range(i,j+1):\n                    a = dp[i][k-1] if k>i else 0\n                    b = dp[k+1][j] if k<j else 0\n                    dp[i][j] = max(dp[i][j],nums[i-1]*nums[k]*nums[j+1] + a + b)\n                    \n        return dp[1][len(nums)-2]\n\t\t\n\t# Another implementation\t\n    def maxCoins(self, nums: List[int]) -> int:\n        nums = [1] + nums + [1]\n        dp = [[0]*len(nums) for i in range(len(nums))]\n        \n        for i in range(len(nums)-2,0,-1):\n            for j in range(i,len(nums)-1):\n                for k in range(i,j+1):\n                    a = dp[i][k-1] if k>i else 0\n                    b = dp[k+1][j] if k<j else 0\n                    dp[i][j] = max(dp[i][j],nums[i-1]*nums[k]*nums[j+1] + a + b)\n                    \n        return dp[1][len(nums)-2]\n```
['Dynamic Programming', 'Python3']