Minimum Score Triangulation of Polygon

Problem

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.

Examples

Example 1

Input: values = [1,2,3]
Output: 6
Explanation: The polygon is already triangulated, and the score of the only triangle is 6.

Example 2

Input: values = [3,7,4,5]
Output: 144
Explanation: There are two triangulations, with possible scores: 3*7*5 + 4*5*7 = 245, or 3*4*5 + 3*4*7 = 144.
The minimum score is 144.

Example 3

Input: values = [1,3,1,4,1,5]
Output: 13
Explanation: The minimum score triangulation is 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.

Constraints

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

Solution

We exploit the fact that any optimal triangulation of a convex polygon is formed by choosing, for each sub-polygon (interval of vertices) [i..j], one vertex k (i < k < j) to make triangle (i,k,j) plus optimal triangulations of the two resulting sub-polygons (i..k) and (k..j).

Method 1 - Naive Recursion (Exponential)

Intuition

Pick every possible third vertex k between i and j to form triangle (i,k,j), then recursively solve the left and right sub-polygons. This brute-force explores all Catalan-like partitions with massive recomputation.

Approach

• Define solve(i,j) = minimum score to triangulate vertices from i to j (inclusive).
• Base: if j - i < 2 (fewer than 3 vertices) return 0 (no triangle possible).
• Otherwise try each k in (i+1 .. j-1) and minimize: solve(i,k) + values[i]*values[k]*values[j] + solve(k,j).

Recurrence

solve(i,j) = 0                              if j - i < 2
solve(i,j) = min_{i<k<j} solve(i,k) + values[i]*values[k]*values[j] + solve(k,j)

Code

C++

class SolutionNaive {
public:
    int minScoreTriangulation(std::vector<int>& values) {
        int n = values.size();
        return dfs(values, 0, n-1);
    }
private:
    int dfs(const std::vector<int>& v, int i, int j) {
        if (j - i < 2) return 0;
        int best = INT_MAX;
        for (int k = i + 1; k < j; ++k) {
            best = std::min(best, dfs(v,i,k) + v[i]*v[k]*v[j] + dfs(v,k,j));
        }
        return best;
    }
};

Java

class SolutionNaive {
    public int minScoreTriangulation(int[] values) {
        return dfs(values, 0, values.length - 1);
    }
    private int dfs(int[] v, int i, int j) {
        if (j - i < 2) return 0;
        int best = Integer.MAX_VALUE;
        for (int k = i + 1; k < j; k++) {
            best = Math.min(best, dfs(v,i,k) + v[i]*v[k]*v[j] + dfs(v,k,j));
        }
        return best;
    }
}

Python

class SolutionNaive:
    def minScoreTriangulation(self, values: list[int]) -> int:
        from math import inf
        def dfs(i: int, j: int) -> int:
            if j - i < 2:
                return 0
            best = inf
            for k in range(i+1, j):
                best = min(best, dfs(i,k) + values[i]*values[k]*values[j] + dfs(k,j))
            return best
        return dfs(0, len(values)-1)

Complexity

• ⏰ Time complexity: O(Catalan) – exponential due to repeated subproblems.
• 🧺 Space complexity: O(n) – recursion depth.

Method 2 - Top-Down Memoization (Interval DP)

Intuition

The naive recursion recomputes identical intervals (i,j). Cache them to reduce to O(n^3) since there are O(n^2) intervals and each tries O(n) splits.

Approach

• Memo table dp[i][j] initialized to -1 / None.
• On each call, return cached value if present.
• Same recurrence as Method 1.

Recurrence

dp[i][j] = 0                          if j - i < 2
dp[i][j] = min_{i<k<j} dp[i][k] + values[i]*values[k]*values[j] + dp[k][j]

Code

C++

class SolutionMemo {
public:
    int minScoreTriangulation(std::vector<int>& values) {
        int n = values.size();
        memo.assign(n, std::vector<int>(n, -1));
        return solve(values, 0, n-1);
    }
private:
    std::vector<std::vector<int>> memo;
    int solve(const std::vector<int>& v, int i, int j) {
        if (j - i < 2) return 0;
        int &ref = memo[i][j];
        if (ref != -1) return ref;
        int best = INT_MAX;
        for (int k = i + 1; k < j; ++k)
            best = std::min(best, solve(v,i,k) + v[i]*v[k]*v[j] + solve(v,k,j));
        return ref = best;
    }
};

Java

class SolutionMemo {
    private int[][] dp;
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        dp = new int[n][n];
        for (int i = 0; i < n; i++)
            java.util.Arrays.fill(dp[i], -1);
        return solve(values, 0, n-1);
    }
    private int solve(int[] v, int i, int j) {
        if (j - i < 2) return 0;
        if (dp[i][j] != -1) return dp[i][j];
        int best = Integer.MAX_VALUE;
        for (int k = i + 1; k < j; k++) {
            best = Math.min(best, solve(v,i,k) + v[i]*v[k]*v[j] + solve(v,k,j));
        }
        dp[i][j] = best;
        return best;
    }
}

Python

from functools import lru_cache

class SolutionMemo:
    def minScoreTriangulation(self, values: list[int]) -> int:
        @lru_cache(None)
        def solve(i: int, j: int) -> int:
            if j - i < 2:
                return 0
            best = float('inf')
            for k in range(i+1, j):
                best = min(best, solve(i,k) + values[i]*values[k]*values[j] + solve(k,j))
            return best
        return solve(0, len(values)-1)

Complexity

• ⏰ Time complexity: O(n^3) – O(n^2) intervals × O(n) splits.
• 🧺 Space complexity: O(n^2) memo table + recursion stack O(n).

Method 3 - Bottom-Up DP (Iterative Interval Filling)

Intuition

Fill increasing interval lengths so that when computing dp[i][j], all smaller sub-intervals are already solved. Classic interval DP ordering.

Approach

1. Initialize dp[i][j]=0 for j-i<2 (implicit by zeros).
2. For length len from 3 to n, iterate start i, end j=i+len-1.
3. For each k in (i+1..j-1) update dp[i][j] with recurrence.
4. Return dp[0][n-1].

Recurrence

Same as above: dp[i][j] = min_{i<k<j} dp[i][k] + v[i]*v[k]*v[j] + dp[k][j].

Code

C++

class Solution {
public:
    int minScoreTriangulation(std::vector<int>& values) {
        int n = values.size();
        std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
        for (int len = 3; len <= n; ++len) {
            for (int i = 0; i + len <= n; ++i) {
                int j = i + len - 1;
                int best = INT_MAX;
                for (int k = i + 1; k < j; ++k)
                    best = std::min(best, dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]);
                dp[i][j] = best;
            }
        }
        return dp[0][n-1];
    }
};

Java

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 + len <= n; ++i) {
                int j = i + len - 1;
                int best = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; ++k)
                    best = Math.min(best, dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]);
                dp[i][j] = best;
            }
        }
        return dp[0][n-1];
    }
}

Python

class Solution:
    def minScoreTriangulation(self, values: list[int]) -> int:
        n = len(values)
        dp = [[0]*n for _ in range(n)]
        for length in range(3, n+1):
            for i in range(0, n - length + 1):
                j = i + length - 1
                best = float('inf')
                for k in range(i+1, j):
                    best = min(best, dp[i][k] + dp[k][j] + values[i]*values[k]*values[j])
                dp[i][j] = best
        return dp[0][n-1]

Kotlin

class SolutionK {
    fun minScoreTriangulation(values: IntArray): Int {
        val n = values.size
        val dp = Array(n) { IntArray(n) }
        for (len in 3..n) {
            for (i in 0..n-len) {
                val j = i + len - 1
                var best = Int.MAX_VALUE
                for (k in i+1 until j) {
                    best = minOf(best, dp[i][k] + dp[k][j] + values[i]*values[k]*values[j])
                }
                dp[i][j] = best
            }
        }
        return dp[0][n-1]
    }
}

TypeScript

class SolutionTS {
    minScoreTriangulation(values: number[]): number {
        const n = values.length;
        const dp: number[][] = Array.from({length: n}, () => Array(n).fill(0));
        for (let len = 3; len <= n; len++) {
            for (let i = 0; i + len <= n; i++) {
                const j = i + len - 1;
                let best = Infinity;
                for (let k = i + 1; k < j; k++)
                    best = Math.min(best, dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]);
                dp[i][j] = best;
            }
        }
        return dp[0][n-1];
    }
}

Rust

impl Solution {
    pub fn min_score_triangulation(values: Vec<i32>) -> i32 {
        let n = values.len();
        let mut dp = vec![vec![0; n]; n];
        for len in 3..=n {
            for i in 0..=n-len {
                let j = i + len - 1;
                let mut best = i32::MAX;
                for k in i+1..j {
                    let cand = dp[i][k] + dp[k][j] + values[i]*values[k]*values[j];
                    if cand < best { best = cand; }
                }
                dp[i][j] = best;
            }
        }
        dp[0][n-1]
    }
}

Complexity

• ⏰ Time complexity: O(n^3) – n^2 intervals × n splits.
• 🧺 Space complexity: O(n^2) – DP table.