Python || 91.95% Faster || DP || 3 solutions
\n#Recursive\n#Time Complexity: Exponential\n#Space Complexity: O(n)\nclass Solution1:\n    def minScoreTriangulation(self, values: List[int]) -> int:\n        
```\n#Recursive\n#Time Complexity: Exponential\n#Space Complexity: O(n)\nclass Solution1:\n    def minScoreTriangulation(self, values: List[int]) -> int:\n        def solve(i, j):\n            if i+1 == j:\n                return 0\n            m = float(\'inf\')\n            for k in range(i+1, j):\n                m = min(m, values[i] * (values[j]*values[k]) + solve(i, k) + solve(k, j))\n            return m\n        return solve(0, len(values)-1)\n    \n#Memoization (Top-Down)\n#Time Complexity: O(n^2)\n#Space Complexity: O(n^2) + O(n)\nclass Solution2:\n    def minScoreTriangulation(self, values: List[int]) -> int:\n        def solve(i, j):\n            if i+1 == j:\n                return 0\n            if dp[i][j] != -1:\n                return dp[i][j]\n            m = float(\'inf\')\n            for k in range(i+1, j):\n                m = min(m, values[i] * (values[j]*values[k]) + solve(i, k) + solve(k, j))\n            dp[i][j] = m\n            return dp[i][j]\n        \n        n = len(values)\n        dp = [[-1 for j in range(n)] for i in range(n)]\n        return solve(0, n-1)\n\n#Tabulation (Bottom-Up)\n#Time Complexity: O(n^2)\n#Space Complexity: O(n^2)\nclass Solution:\n    def minScoreTriangulation(self, values: List[int]) -> int:\n        n = len(values)\n        dp = [[0 for j in range(n)] for i in range(n)]\n        for i in range(n-1, -1, -1):\n            for j in range(i+2, n):\n                m = float(\'inf\')\n                for k in range(i+1, j):\n                    m = min(m, values[i]*values[j]*values[k] + dp[i][k] + dp[k][j])\n                dp[i][j] = m\n        return dp[0][n-1]\n```\n**An upvote will be encouraging**
['Dynamic Programming', 'Recursion', 'Memoization', 'Python', 'Python3']