Simple Python DFS with Explanation (12 lines)
the intuition here is that l and r are ALWAYS going to be in a triange\nwe just need to figure out the third point in the triangle\npossible third points are al
the intuition here is that l and r are ALWAYS going to be in a triange\nwe just need to figure out the third point in the triangle\npossible third points are all indices between l and r\n\nonce you draw the lines between l, r and some i between l and r\nyou have two subproblems and one triangle\ntwo subproblems are l to i, and i to r\none triange is the triangle with indices l,r,i\n\nin the case where i=l+1, or i=r-1 we have two established sides of the triangle\nwhen i=l+1 we already have (l,i), (r,l)\nwhen i=r-1 we already have (r-1,r), (r,l)\n \nin the case where l+1 < i < r-1\nimagine the third index is somewhere in the middle of the polygon\nyou can imagine drawing two new lines (l,i) and (i,r)\nthen you have the two subproblems\n\n```\nfrom functools import cache\nclass Solution:\n    def minScoreTriangulation(self, values: List[int]) -> int:\n        @cache\n        def dfs(l, r):\n            if r-l+1 < 3:\n                return 0\n            m = float(\'inf\')\n            for i in range(l+1, r):\n                m = min(m, dfs(l, i) + dfs(i, r) + values[l]*values[r]*values[i])\n            return m\n        return dfs(0, len(values)-1)\n```
['Depth-First Search', 'Python']