Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

In any triangulation of the polygon interval from vertex i to j, exactly one triangle touches its boundary edge (i, j). Choosing that triangle's third vertex splits the remaining work into two independent smaller polygon intervals.

Approach

Memoize the minimum score for each interval (i, j). An interval with fewer than three vertices costs zero. Otherwise try every k strictly between its endpoints, adding values[i] * values[k] * values[j] to the optimal scores for (i, k) and (k, j). Keep the minimum and evaluate the full interval. Convexity ensures these splits are legal, and considering every third vertex covers every possible triangulation.

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        @cache
        def dp(i, j):
            if j - i < 2:
                return 0
            # no triangle

            res = float('inf')

            for k in range(i + 1, j):
                curr = values[i] * values[j] * values[k]
                res = min(res, curr + dp(i, k) + dp(k, j))
                # try curr and split

            return res

        return dp(0, len(values) - 1)

Complexity analysis

For n vertices, there are O(n²) cached intervals and each tries O(n) split points, giving O(n³) time and O(n²) memo space plus O(n) recursion depth.