The tricky point: find a way to divide the problem
Foremost, I want to say this problem is not good for interview because it depends a tricky insights about how to divide the problem. For the record, I\'ve never
Foremost, I want to say this problem is not good for interview because it depends a tricky insights about how to divide the problem. For the record, I\'ve never encountered this hard problems in any top tier company(FB, Google) from L3 to L6 interviews(coding is hardest at L3 and L4).\n\nThere are multiple ways to divide and conqur, however, it\'s tough to find a scheme where the number of subproblems is small enough so as to memorized(or DP if you wish).\n\nI spent over one hour to find one such scheme: for one edge in the original polygon, it must be connected with one \'other\' vertex to form a triangle(other means not the two vertex making the edge). Iterate all such vertexes, each vertex correspond to one way of dividing the orignial problem. Recursively divide and conqure. I always use memorized search since it\'s much easier to reason with and impelment.\n\n```python\nclass Solution:\n  def minScoreTriangulation(self, arr: List[int]) -> int:\n    n = len(arr)\n    \n    @lru_cache(None)\n    def solve(begin, end):\n      if (begin + 1) % n == end:\n        return 0\n      \n      ret = -1\n      \n      split = (begin + 1) % n\n      while split != end:\n        cur = arr[begin] * arr[end] * arr[split] + solve(begin, split) + solve(split, end)\n        if ret == -1 or ret > cur:\n          ret = cur\n        split = (split + 1) % n\n      return ret\n    \n    return solve(0, n - 1)\n```
[]