python, dynamic programming solution with explanation
dp[i][j] means min score get from values[i:j+1] -> closed interval[i, j]\ndp[i][j] = (1) + (2) + (3) =min(dp[i][k] + dp[k][j] + values[i] * values[k] * values[j
```dp[i][j]``` means min score get from ```values[i:j+1]``` -> closed interval```[i, j]```\n```dp[i][j] = (1) + (2) + (3) =min(dp[i][k] + dp[k][j] + values[i] * values[k] * values[j] for k in closed interval [i+1,j-1])```\n```\n     j            i\n       --------------\n\t /  \\         |   \\\n    /     \\  (3)  |    \\\n   /       \\      | (1) \\\n   \\         \\    |     /\n\t\\   (2)    \\  |    /\n\t \\          \\ |   /\n\t   -------------- \n                    k\n```\neg. values=```[3,7,4,5,9]```\n<img src="https://latex.codecogs.com/svg.image?\\begin{bmatrix}&space;&&space;3&space;&&space;7&space;&&space;4&space;&&space;5&space;&&space;9&space;\\\\3&space;&&space;0&space;&&space;0&space;&&space;84&space;&&space;144&space;&&space;279&space;\\\\7&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;140&space;&&space;432&space;\\\\4&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;180&space;\\\\5&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;\\\\9&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;&&space;0&space;\\end{bmatrix}" />\n### iteration\ntc is ```O(len(value)**3)```, sc is ```O(len(value)**2)```\n``` python\nclass Solution:\n    def minScoreTriangulation(self, values: List[int]) -> int:\n        if len(values) == 3: return values[0] * values[1] * values[2]\n        leng = len(values)\n        dp = [[0]*leng for _ in range(leng)]\n        for i in range(leng-3, -1, -1):\n            for j in range(i, leng):\n                for k in range(i+1, j):\n                    if dp[i][j] == 0:\n                        dp[i][j] = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]\n                    else:\n                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i]*values[k]*values[j])\n        return dp[0][leng-1]\n```\n\n### dfs\ntc is ```O(len(value)**3)```, sc is ```O(len(value)**2)```\n``` python\nmax_ = 2**31 - 1\nclass Solution:\n    def minScoreTriangulation(self, values: List[int]) -> int:\n        if len(values) == 3: return values[0] * values[1] * values[2]\n        @cache\n        def dfs(i, j):\n            if j-i <= 1: return 0 # there is no triangle between neighbor\n            ans = max_\n            for k in range(i+1, j):\n                ans = min(ans, dfs(i,k) + dfs(k,j) + values[i] * values[k] * values[j])\n            return ans\n        return dfs(0, len(values)-1)\n```
['Dynamic Programming', 'Python']