Python || 90.12% Faster || DP || Recursive->Tabulation
\n#Recursion \n#Time Complexity: O(Exponential)\n#Space Complexity: O(n)\nclass Solution1:\n    def maxCoins(self, nums: List[int]) -> int:\n        def solve(i
```\n#Recursion \n#Time Complexity: O(Exponential)\n#Space Complexity: O(n)\nclass Solution1:\n    def maxCoins(self, nums: List[int]) -> int:\n        def solve(i,j):\n            if i>j:\n                return 0\n            maxi=-maxsize\n            for k in range(i,j+1):\n                coins=nums[i-1]*nums[k]*nums[j+1]+solve(i,k-1)+solve(k+1,j)\n                maxi=max(maxi,coins)\n            return maxi\n        \n        n=len(nums)\n        nums.insert(0,1)\n        nums.append(1)\n        return solve(1,n)\n    \n#Memoization (Top-Down)\n#Time Complexity: O(n^3)\n#Space Complexity: O(n^2) + O(n)\nclass Solution2:\n    def maxCoins(self, nums: List[int]) -> int:\n        def solve(i,j):\n            if i>j:\n                return 0\n            if dp[i][j]!=-1:\n                return dp[i][j]\n            maxi=-maxsize\n            for k in range(i,j+1):\n                coins=nums[i-1]*nums[k]*nums[j+1]+solve(i,k-1)+solve(k+1,j)\n                maxi=max(maxi,coins)\n            dp[i][j]=maxi\n            return dp[i][j]\n        \n        n=len(nums)\n        dp=[[-1 for j in range(n+1)] for j in range(n+1)]\n        nums.insert(0,1)\n        nums.append(1)\n        return solve(1,n)\n    \n#Tabulation (Bottom-Up)\n#Time Complexity: O(n^3)\n#Space Complexity: O(n^2)\nclass Solution:\n    def maxCoins(self, nums: List[int]) -> int:\n        n=len(nums)\n        nums.insert(0,1)\n        nums.append(1)\n        dp=[[0 for j in range(n+2)] for j in range(n+2)]\n        for i in range(n,0,-1):\n            for j in range(1,n+1):\n                if i>j:\n                    continue\n                maxi=-maxsize\n                for k in range(i,j+1):\n                    coins=nums[i-1]*nums[k]*nums[j+1]+dp[i][k-1]+dp[k+1][j]\n                    maxi=max(maxi,coins)\n                dp[i][j]=maxi\n        return dp[1][n]\n```\n**An upvote will be encouraging**
['Dynamic Programming', 'Recursion', 'Memoization', 'Python', 'Python3']