We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Score Triangulation of Polygon

Difficulty: Medium

Problem Description

You have a convex n-sided polygon where each vertex has an integer value. You are given an integer array values where values[i] is the value of the ith vertex in clockwise order. Polygon triangulation is a process where you divide a polygon into a set of triangles and the vertices of each triangle must also be vertices of the original polygon. Note that no other shapes other than triangles are allowed in the division. This process will result in n - 2 triangles. You will triangulate the polygon. For each triangle, the weight of that triangle is the product of the values at its vertices. The total score of the triangulation is the sum of these weights over all n - 2 triangles. Return the minimum possible score that you can achieve with some triangulation of the polygon.

Key Insights

  • The problem can be solved using Dynamic Programming by breaking it down into smaller subproblems.
  • The score for every triangle formed by three vertices can be represented as a product of their values.
  • The optimal triangulation of larger sub-polygons can be found using previously computed results of smaller sub-polygons.
  • The minimum score can be computed by iterating through possible triangles and calculating the total score recursively, while memoizing results to avoid redundant calculations.

Space and Time Complexity

Time Complexity: O(n^3)
Space Complexity: O(n^2)

Solution

To solve the problem, we will use a Dynamic Programming approach. We will maintain a 2D array dp where dp[i][j] represents the minimum score to triangulate the polygon formed by the vertices from index i to j. The main idea is to iterate through all possible triangles that can be formed by choosing a vertex k between i and j, where the triangle is formed by vertices i, j, and k. The score for this triangle is calculated as values[i] * values[j] * values[k]. We will then combine this with the minimum scores of the two resulting sub-polygons: from i to k and from k to j. We will update our dp table accordingly to find the minimum score for the polygon.

Code Solutions

def minScoreTriangulation(values):
    n = len(values)
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n):  # length of the polygon side
        for i in range(n - length):
            j = i + length
            dp[i][j] = float('inf')  # Initialize to infinity
            for k in range(i + 1, j):
                score = values[i] * values[j] * values[k]
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + score)
    
    return dp[0][n - 1]
← Back to All Questions