Minimum Score Triangulation of Polygon

medium dynamic programming interval dp polygon

Problem

You have a convex polygon with n vertices, labeled in clockwise order by an array values where values[i] is the value of the i-th vertex. Any triangulation of the polygon into n − 2 triangles assigns each triangle a score equal to the product of its three vertex values; the total score of a triangulation is the sum of these triangle scores. Return the smallest possible total score over all triangulations.

Inputvalues = [1, 3, 1, 4, 1, 5]

Output13

One optimal triangulation yields total score 13; no other split produces a smaller sum of triangle products.

values (comma-separated, 3–8 vertices)

def min_score_triangulation(values):
    n = len(values)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            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]

function minScoreTriangulation(values) {
  const n = values.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let len = 2; len < n; len++) {
    for (let i = 0; i + len < n; i++) {
      const j = i + len;
      dp[i][j] = Infinity;
      for (let k = i + 1; k < j; k++) {
        const 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];
}

class Solution {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];
        for (int len = 2; len < n; len++) {
            for (int i = 0; i + len < n; i++) {
                int j = i + len;
                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];
    }
}

int minScoreTriangulation(vector<int>& values) {
    int n = values.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 2; len < n; len++) {
        for (int i = 0; i + len < n; i++) {
            int j = i + len;
            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];
}

Explanation

Cutting a convex polygon into triangles always leaves one triangle resting on the edge between the first and last vertex of any range. That single observation turns this into an interval DP over vertex ranges.

dp[i][j] is the minimum score to triangulate the sub-polygon spanning vertices i through j. We pick an apex vertex k between i and j: the triangle (i, k, j) scores values[i] * values[k] * values[j], and the two sides become independent subproblems dp[i][k] and dp[k][j].

We try every apex k and keep the smallest total, processing ranges from short to long so the inner pieces are already computed. Ranges of length 1 (a single edge) have score 0.

Example: values = [1,3,1,4,1,5]. Choosing the apexes that pair the small values together keeps each triangle's product low, and the best overall total is 13, found at dp[0][n-1].

With O(n²) ranges and up to O(n) apex choices each, the algorithm runs in O(n³).

Time: O(n³) Space: O(n²)