Minimum Score Triangulation of Polygon - Solution & Explanation

This problem is a classic example of Dynamic Programming. The idea is to partition the polygon using dynamic programming where you maintain a dp table, dp[i][j] represents the minimum score to triangulate a polygon starting from vertex i to vertex j.

To solve the problem, we iterate through all possible partitions and calculate their respective scores, updating the dp table to reflect the minimum scores possible for triangulating various sub-polygons.

This C code uses a dynamic programming approach to solve the polygon triangulation problem. The dp table, dp[i][j], stores the minimum score for triangulating the sub-polygon from vertex i to vertex j. We iterate over possible lengths len of the sub-polygons, then calculate the minimum score considering the product of the chosen vertices.

We design a function dfs(i, j), which represents the minimum score after triangulating the polygon from vertex i to j. The answer is dfs(0, n - 1).

The calculation process of dfs(i, j) is as follows:

• If i + 1 = j, it means the polygon has only two vertices and cannot be triangulated, so we return 0;
• Otherwise, we enumerate a vertex k between i and j, i.e., i \lt k \lt j. Triangulating the polygon from vertex i to j can be divided into two subproblems: triangulating the polygon from vertex i to k and triangulating the polygon from vertex k to j. The minimum scores of these two subproblems are dfs(i, k) and dfs(k, j), respectively. The score of the triangle formed by vertices i, j, and k is values[i] times values[k] times values[j]. Thus, the minimum score for this triangulation is dfs(i, k) + dfs(k, j) + values[i] times values[k] times values[j]. We take the minimum value of all possibilities, which is the value of dfs(i, j).

To avoid repeated calculations, we can use memoization, i.e., use a hash table or an array to store the already computed function values.

Finally, we return dfs(0, n - 1).

The time complexity is O(n^3), and the space complexity is O(n^2), where n is the number of vertices in the polygon.

We can convert the memoization approach in Solution 1 into a dynamic programming approach.

Define f[i][j] as the minimum score after triangulating the polygon from vertex i to j. Initially, f[i][j] = 0, and the answer is f[0][n-1].

For f[i][j] (where i + 1 \lt j), we first initialize f[i][j] to infty.

We enumerate a vertex k between i and j, i.e., i \lt k \lt j. Triangulating the polygon from vertex i to j can be divided into two subproblems: triangulating the polygon from vertex i to k and triangulating the polygon from vertex k to j. The minimum scores of these two subproblems are f[i][k] and f[k][j], respectively. The score of the triangle formed by vertices i, j, and k is values[i] times values[k] times values[j]. Thus, the minimum score for this triangulation is f[i][k] + f[k][j] + values[i] times values[k] times values[j]. We take the minimum value of all possibilities, which becomes the value of f[i][j].

In summary, we can derive the state transition equation:

$ f[i][j]= \begin{cases} 0, & i+1=j \ infty, & i+1<j \ min_{i<k<j} {f[i][k]+f[k][j]+values[i] times values[k] times values[j]}, & i+1<j \end{cases}

Note that when enumerating i and j, there are two possible enumeration strategies:

1. Enumerate i from large to small and j from small to large. This ensures that when calculating the state f[i][j], the states f[i][k] and f[k][j] have already been computed.
2. Enumerate the interval length l from small to large, where 3 leq l leq n. Then enumerate the left endpoint i of the interval, and the right endpoint can be calculated as j = i + l - 1. This also ensures that when calculating the larger interval f[i][j], the smaller intervals f[i][k] and f[k][j] have already been computed.

Finally, we return f[0][n-1].

The time complexity is O(n^3), and the space complexity is O(n^2), where n$ is the number of vertices in the polygon.

Related problems:

• 1312. Minimum Insertion Steps to Make a String Palindrome

In Solution 2, we mentioned two enumeration strategies. Here, we use the second strategy: enumerate the interval length l from small to large, where 3 leq l leq n. Then, enumerate the left endpoint i of the interval, and the right endpoint can be calculated as j = i + l - 1.

The time complexity is O(n^3), and the space complexity is O(n^2), where n is the number of vertices in the polygon.