Minimum Score Triangulation of Polygon

Medium
1478.

Minimum Score Triangulation of Polygon

Minimum Score Triangulation of Polygon is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Uber interviews.

A convex polygon has n vertices, and values[i] is the label of the i-th vertex in clockwise order.

Cut the polygon into n - 2 triangles using non-crossing diagonals (a triangulation). Each triangle scores the product of the labels of its three vertices, and a triangulation scores the sum of its triangles' scores.

Return the smallest score any triangulation can achieve.

Example 1

Input
values = [2,4,3]
Output
24
Explanation
Already a triangle: 2 · 4 · 3.

Example 2

Input
values = [1,5,2,4]
Output
18
Explanation
Diagonal 0–2 gives 1·5·2 + 1·2·4 = 18; diagonal 1–3 gives 60.

Example 3

Input
values = [1,3,1,4,1,5]
Output
13

Constraints

  • n == values.length
  • 3 <= n <= 50
  • 1 <= values[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} values
 * @return {number}
 */
var minScoreTriangulation = function(values) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Score Triangulation of Polygon — Problem & Solution

Minimum Score Triangulation of Polygon solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Score Triangulation of Polygon is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Uber interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google, Uber
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A convex polygon has n vertices, and values[i] is the label of the i-th vertex in clockwise order.

Cut the polygon into n - 2 triangles using non-crossing diagonals (a triangulation). Each triangle scores the product of the labels of its three vertices, and a triangulation scores the sum of its triangles' scores.

Return the smallest score any triangulation can achieve.

Example 1

Input: values = [2,4,3]
Output: 24
Explanation: Already a triangle: 2 · 4 · 3.

Example 2

Input: values = [1,5,2,4]
Output: 18
Explanation: Diagonal 0–2 gives 1·5·2 + 1·2·4 = 18; diagonal 1–3 gives 60.

Example 3

Input: values = [1,3,1,4,1,5]
Output: 13

Constraints

  • n == values.length
  • 3 <= n <= 50
  • 1 <= values[i] <= 100

Hints for Minimum Score Triangulation of Polygon

  1. Hint 1

    In any triangulation, the edge between vertex 0 and vertex n-1 belongs to exactly one triangle.

  2. Hint 2

    If that triangle's third vertex is k, the rest splits into two independent smaller polygons: 0..k and k..n-1.

  3. Hint 3

    Let dp[i][j] be the best score for the polygon formed by vertices i..j; try every k strictly between them.

How to solve Minimum Score Triangulation of Polygon

Interval DP. For the sub-polygon on vertices i..j, the side (i, j) lies in exactly one triangle (i, k, j), and choosing k splits the remainder into the sub-polygons i..k and k..j.

Approach

  1. dp[i][j] = 0 when j - i < 2 (an edge, nothing to triangulate).
  2. For increasing gap j - i from 2 to n - 1: dp[i][j] = min over i < k < j of dp[i][k] + dp[k][j] + values[i]·values[k]·values[j].
  3. Return dp[0][n-1].

Why it works

Every triangulation of i..j contains exactly one triangle on the side (i, j), and the diagonals (i, k) and (k, j) separate the rest into two polygons that are triangulated independently. Taking the minimum over all k therefore covers every triangulation, and the two halves can each be chosen optimally on their own.

Complexity

  • Time — O(n³)
  • Space — O(n²)

Pitfalls

  • Fill the table by increasing interval length so both halves are ready.
  • The polygon is cyclic, but fixing the side (0, n-1) removes the need for wrap-around.
  • The answer can reach about 5·10^7, which fits in 32 bits — no modulus is involved.

Reference solution

Python

from typing import List

def minScoreTriangulation(values: List[int]) -> int:
    n = len(values)
    dp = [[0] * n for _ in range(n)]
    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            best = -1
            for k in range(i + 1, j):
                cand = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]
                if best < 0 or cand < best:
                    best = cand
            dp[i][j] = best
    return dp[0][n - 1]

Java

public static int minScoreTriangulation(int[] values) {
    int n = values.length;
    int[][] dp = new int[n][n];
    for (int gap = 2; gap < n; gap++) {
        for (int i = 0; i + gap < n; i++) {
            int j = i + gap;
            int best = -1;
            for (int k = i + 1; k < j; k++) {
                int cand = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
                if (best < 0 || cand < best) best = cand;
            }
            dp[i][j] = best;
        }
    }
    return dp[0][n - 1];
}

C++

int minScoreTriangulation(vector<int>& values) {
    int n = values.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int gap = 2; gap < n; gap++) {
        for (int i = 0; i + gap < n; i++) {
            int j = i + gap;
            int best = -1;
            for (int k = i + 1; k < j; k++) {
                int cand = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
                if (best < 0 || cand < best) best = cand;
            }
            dp[i][j] = best;
        }
    }
    return dp[0][n - 1];
}

JavaScript

var minScoreTriangulation = function(values) {
    var n = values.length;
    var dp = [];
    for (var i = 0; i < n; i++) dp.push(new Array(n).fill(0));
    for (var gap = 2; gap < n; gap++) {
        for (i = 0; i + gap < n; i++) {
            var j = i + gap;
            var best = -1;
            for (var k = i + 1; k < j; k++) {
                var cand = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
                if (best < 0 || cand < best) best = cand;
            }
            dp[i][j] = best;
        }
    }
    return dp[0][n - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming