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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Score Triangulation of Polygon

Number: 1111

Difficulty: Medium

Paid? No

Companies: Google, Adobe, Amazon, Uber

Problem Description

Given a convex polygon with n vertices, each vertex has an integer value provided in a list in clockwise order. The task is to triangulate the polygon (divide it into n-2 triangles using the vertices) such that the total score is minimized. The score of each triangle is defined as the product of the three vertex values that form the triangle, and the total score is the sum of the scores of all triangles.

Key Insights

  • The problem can be solved using dynamic programming by considering sub-polygons.
  • Define dp[i][j] as the minimum score to triangulate the polygon spanning from vertex i to vertex j.
  • The recurrence relation is: dp[i][j] = min(dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]) for all k where i < k < j.
  • The final answer is found in dp[0][n-1].
  • The subproblems build on smaller polygons and are solved in increasing order of polygon length.

Space and Time Complexity

Time Complexity: O(n^3) – by iterating over all pairs (i, j) and considering every k between them. Space Complexity: O(n^2) – used for storing the dp table.

Solution

The solution uses a dynamic programming (DP) approach to break down the polygon triangulation problem into smaller subproblems. We initialize a 2D array dp where dp[i][j] represents the minimum triangulation cost for the sub-polygon between indices i and j. For every possible sub-polygon (with increasing length), we try every possible triangle that can be formed by picking an intermediate vertex k. The triangle formed by vertices i, k, and j contributes a cost of values[i] * values[k] * values[j]. We add this to the optimal triangulation costs of the two resulting sub-polygons (dp[i][k] and dp[k][j]) and update dp[i][j] with the minimum cost found. Finally, dp[0][n-1] holds the minimum cost for triangulating the entire polygon.

Code Solutions

# Python solution for minimum score triangulation of polygon

def minScoreTriangulation(values):
    n = len(values)  # Obtain the number of vertices in the polygon
    # Initialize DP table with zeros; table dimensions: n x n
    dp = [[0] * n for _ in range(n)]
    
    # Calculate minimum triangulation cost for sub-polygons of increasing length
    # length: current sub-polygon length from i to j
    for length in range(2, n):
        # Iterate over all possible start indices i for the sub-polygon
        for i in range(0, n - length):
            j = i + length  # end index of the sub-polygon
            dp[i][j] = float('inf')  # initialize with infinity
            # k is a vertex between i and j that splits the polygon into two parts
            for k in range(i + 1, j):
                # cost of triangle (i, k, j) plus cost of sub-polygons
                cost = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]
                dp[i][j] = min(dp[i][j], cost)  # update minimum cost found
    # The minimum triangulation cost for the full polygon is stored in dp[0][n-1]
    return dp[0][n-1]

# Example usage
print(minScoreTriangulation([3,7,4,5]))  # Expected output: 144
← Back to All Questions