Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1039. Minimum Score Triangulation of Polygon - Leetcode Solution

Code Implementation

class Solution:
    def minScoreTriangulation(self, values):
        n = len(values)
        dp = [[0] * n for _ in range(n)]
        # dp[i][j]: min score to triangulate polygon from i to j
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = float('inf')
                for k in range(i + 1, j):
                    cost = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]
                    dp[i][j] = min(dp[i][j], cost)
        return dp[0][n - 1]
      
class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int length = 3; length <= n; ++length) {
            for (int i = 0; i <= n - length; ++i) {
                int j = i + length - 1;
                dp[i][j] = INT_MAX;
                for (int k = i + 1; k < j; ++k) {
                    int cost = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
                    dp[i][j] = min(dp[i][j], cost);
                }
            }
        }
        return dp[0][n - 1];
    }
};
      
class Solution {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; k++) {
                    int cost = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }
        return dp[0][n - 1];
    }
}
      
var minScoreTriangulation = function(values) {
    const n = values.length;
    const dp = Array.from({length: n}, () => Array(n).fill(0));
    for (let len = 3; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            let j = i + len - 1;
            dp[i][j] = Infinity;
            for (let k = i + 1; k < j; k++) {
                let cost = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n - 1];
};

Problem Description

Given an array values of length n representing the values of vertices of a convex polygon in order, you must triangulate the polygon. Each triangle formed during triangulation has a score equal to the product of its three vertices' values. The total score of a triangulation is the sum of the scores of all triangles formed. Your task is to find the minimum possible total score for a triangulation of the entire polygon.
  • Each triangle must use three different vertices in the order given.
  • You must use all vertices exactly once in the triangulation.
  • There is always at least one valid triangulation for any convex polygon with at least 3 vertices.
  • Return the minimum total score.

Thought Process

When first approaching this problem, you might think about listing all possible ways to split the polygon into triangles and calculating the score for each. However, the number of ways to triangulate a polygon grows rapidly with the number of vertices, making this brute-force approach impractical for larger inputs. To improve on this, notice that the problem has optimal substructure: the minimum triangulation score for the whole polygon can be broken down into the minimum triangulation scores for its sub-polygons. This suggests a dynamic programming approach, where we solve smaller subproblems and combine their results to solve larger ones. The key insight is that, for any interval of vertices, you can try all possible positions to "split" the polygon into two smaller polygons by forming a triangle with the endpoints and one internal vertex, and then recursively solve for the two resulting sub-polygons.

Solution Approach

  • Dynamic Programming Table: Create a 2D array dp where dp[i][j] represents the minimum triangulation score for the sub-polygon from vertex i to vertex j.
  • Base Cases: If the sub-polygon has less than 3 vertices (j - i < 2), it cannot form a triangle, so the score is 0.
  • Recursive Relation: For each possible split point k between i and j (i < k < j), the cost to form a triangle with vertices i, k, and j is values[i] * values[k] * values[j]. The total cost is this triangle's score plus the minimum scores for triangulating the sub-polygons (i, k) and (k, j):
    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j])
  • Filling the Table: Start with the smallest sub-polygons (length 3) and build up to the entire polygon. For each interval (i, j), try all possible k between i and j to find the minimum score.
  • Result: The answer is dp[0][n-1], which represents the minimum triangulation score for the entire polygon.

Example Walkthrough

Let's consider the input values = [1, 3, 1, 4, 1, 5].
  • The polygon has 6 vertices. We want to split it into 4 triangles (since a convex polygon with n vertices can be split into n-2 triangles).
  • We initialize dp[i][j] = 0 for all j - i < 2.
  • We consider all intervals of length 3 (which are triangles) and set their scores directly.
  • For larger intervals, such as i=0, j=3 (vertices 1, 3, 1, 4), we try k=1 and k=2. For each, we compute:
    • For k=1: dp[0][1] + dp[1][3] + 1*3*4
    • For k=2: dp[0][2] + dp[2][3] + 1*1*4
    We pick the minimum.
  • We continue this process for all intervals, eventually computing dp[0][5], which gives the minimum score for the entire polygon.
  • For this input, the minimum triangulation score is 13.

Time and Space Complexity

  • Brute-force: The naive recursive solution without memoization would try all possible ways to split the polygon, leading to exponential time complexity, specifically O(Catalan(n)), which is not feasible for larger n.
  • Dynamic Programming: The optimized DP solution fills an n x n table. For each pair (i, j), we try up to O(n) possible k values. There are O(n^2) pairs, so the total time complexity is O(n^3).
  • Space Complexity: The DP table requires O(n^2) space to store the minimum scores for all sub-polygons.

Summary

This problem demonstrates how dynamic programming can efficiently solve problems with optimal substructure and overlapping subproblems. By breaking the polygon into smaller pieces and reusing solutions to subproblems, we avoid redundant calculations and achieve a much faster solution than brute force. The approach is elegant because it models the problem recursively and builds up the answer using a simple DP table, making the code both efficient and easy to understand.