Problem Statement in English

You have a convex n-sided polygon where each vertex has an integer value.

The vertices are numbered from 0 to n - 1 in clockwise order. You are given an integer array values of length n, where values[i] is the value of the i-th vertex.

You will triangulate the polygon into n - 2 triangles. For each triangle, the score is the product of the values of its vertices, and the total score of the triangulation is the sum of these scores.

Return the minimum possible total score that you can achieve with some triangulation of the polygon.

NOTE: A triangulation of a polygon is a division of the polygon into non-overlapping triangles by drawing non-intersecting diagonals between vertices.

Approach

It’s quite handy to realize that there is no smart way to hack your way through/around this problem. You really need to try out all possible triangulations and pick the one with the minimum score.

This gives us a hint that we can use Dynamic Programming to solve this problem.

The next part is a little whacky. We need to define our subproblems.

The idea is that if you section off a… “polygon section” if I may, into two parts, you can solve each part independently and combine the results.

Here’s a pentagon sectioned off into two parts by drawing a diagonal between vertex 0 and vertex 3:

The cool thing is that now, we can solve the two parts independently and combine the results.

For example, here’s what the green part could be expressed as:

Notice how the green part’s answer was the solution of the beige part and the other green part?

We can exploit this to break every section with >= 3 vertices into two smaller sections, solve each section independently, and combine the results.

Once you read the code you’ll see how this works.

Solution in Python


class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        @cache
        def dp(i, k):
            # if there's less than 3 vertices, we can't form a triangle
            # so return 0
            if k - i < 2:
                return 0

            res = float("inf")
            for j in range(i + 1, k):
                # calculation based on given rules
                res = min(res, dp(i, j) + (values[i] * values[j] * values[k]) + dp(j, k))

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

Complexity

  • Time: $O(n^3)$
    Since we have two parameters (i and k) that can each take n values, and for each pair (i, k), we iterate through j which can also take up to n values.

  • Space: $O(n^2)$
    Since we use a cache to store results of subproblems. The cache is 2D with dimensions n x n.

Mistakes I Made

Had to look this one up :(

And we are done.