Problem statement

https://leetcode.com/problems/minimum-score-triangulation-of-polygon/

Solution

Let dp(i, j) be the minimum cost to cut polygon Ai -> A_{i+1} ... -> A_j -> Ai into triangles, where i < j. Then the segment Ai - Aj must be a side of some triangle i -> k -> j, so we check all cases.

Complexity

It is O(n^3) for time and O(n^2) for space.

Code

class Solution:
    def minScoreTriangulation(self, V):
        @lru_cache(None)
        def dp(i, j):   #i < j?
            if i + 1 == j: return 0
            ans = float("inf")
            for k in range(i + 1, j):
                ans = min(ans, dp(i, k) + dp(k, j) + V[i] * V[j] * V[k])
            return ans
        
        return dp(0, len(V) - 1)