Top-down and bottom-up DP
\nclass Solution:\n    def minScoreTriangulation(self, A: List[int]) -> int:\n        L = len(A)\n        memo = []\n        for i in range(L):\n            mem
```\nclass Solution:\n    def minScoreTriangulation(self, A: List[int]) -> int:\n        L = len(A)\n        memo = []\n        for i in range(L):\n            memo.append([-1 for _ in range(L)])\n            \n        def dp(start, end):\n            if end - start < 2:\n                return 0\n            if end - start == 2:\n                return A[start] * A[start+1] * A[start+2]\n            if memo[start][end] != -1:\n                return memo[start][end]\n            \n            ret = float("inf")\n            for i in range(start+1, end):\n                ret = min(ret, A[start] * A[end] * A[i] + dp(start, i) + dp(i, end))\n            memo[start][end] = ret\n            return ret\n        return dp(0, L-1)\n```\n\n```\nclass Solution:\n    def minScoreTriangulation(self, A: List[int]) -> int:\n        L = len(A)\n        memo = []\n        for start in range(L):\n            memo.append([float("inf") for i in range(L)])\n            memo[start][(start+1) % L] = 0\n            memo[start][(start+2) % L] = A[start] * A[(start+1) % L] * A[(start+2) % L]\n        for delta in range(3, L):\n            for start in range(L):\n                end = start + delta\n                if end >= L: break\n                for i in range(start+1, end):\n                    memo[start][end] = min(memo[start][end], A[start] * A[end] * A[i] + memo[start][i] + memo[i][end])\n                    \n        return memo[0][-1]\n```
[]