Python Simple DP Solution | Faster than 94%
Approach\n Describe your approach to solving the problem. \nWe can solve it with Dynamic programming. DP(pos1,pos2) is the minimum cost of triangulation of vert
# Approach\n<!-- Describe your approach to solving the problem. -->\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# 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```
['Array', 'Dynamic Programming', 'Recursion', 'Python', 'Python3']