Python DP Solution, Faster than 94%
\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nWe can solve it with Dynamic programming. DP(pos1,pos2) is the minimum cost of tri
\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nWe can solve it with Dynamic programming. DP(pos1,pos2) is the minimum cost of triangulation of vertices from pos1 to pos2. if (pos2-pos1<2) return 0 means its not possible to get any triangle. Else, we do DP(pos1,pos2)= min(DP(pos1,pos)+ DP(pos,pos2) + Cost(pos1,pos2,pos))) where Cost(pos1,pos2,k) is the cost of choose triangle with vertices (pos1,pos2,pos) and pos go from pos1+1 to pos2-1\n\n\n# Complexity\n- Time complexity: O(n^3)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minScoreTriangulation(self, values: List[int]) -> int:\n        @cache\n        def dp(pos1: int, pos2: int) -> int:\n            if pos2 - pos1 <= 1:\n                return 0\n            ans = inf\n            for pos in range(pos1 + 1, pos2):\n                ans = min(ans, dp(pos1, pos) + dp(pos, pos2) + values[pos1] * values[pos2] * values[pos])\n            return ans\n\n        return dp(0, len(values) - 1)\n```
['Python3']