# Minimum Score Triangulation of Polygon
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-score-triangulation-of-polygon)
Canonical: https://scaleengineer.com/dsa/problems/minimum-score-triangulation-of-polygon
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## 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.

**Example 1:**

![](http://127.0.0.1:49174/shape1.jpg)

**Input:** values = \[1,2,3\]

**Output:** 6

**Explanation:** The polygon is already triangulated, and the score of the only triangle is 6.

**Example 2:**

![](http://127.0.0.1:49174/shape2.jpg)

**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:**

![](http://127.0.0.1:49174/shape3.jpg)

**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`

# Approaches
## Brute-Force Recursion
This approach directly translates the recursive structure of the problem into a function. The problem of triangulating a polygon with vertices `i` to `j` can be broken down by choosing a third vertex `k` (where `i < k < j`) to form a triangle `(i, k, j)`. This triangle splits the problem into two smaller subproblems: triangulating the polygon from `i` to `k` and triangulating the polygon from `k` to `j`. The total score for this choice of `k` is the sum of the scores of the two subproblems plus the score of the triangle `(i, k, j)`. We try all possible `k` and take the minimum.
**Time:** Exponential, roughly O(2^n). The number of subproblems grows exponentially, leading to a very slow solution. · **Space:** O(n), for the recursion stack depth.
**Pros:** Simple to understand and implement as it directly follows the problem's recursive definition.
**Cons:** Extremely inefficient due to a massive number of re-computations for the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
### Explanation
The core idea is to define a recursive function, say `solve(i, j)`, which calculates the minimum triangulation score for the polygon formed by vertices `values[i], values[i+1], ..., values[j]`. The recurrence relation is:
`solve(i, j) = min_{i < k < j} (solve(i, k) + solve(k, j) + values[i] * values[k] * values[j])`
The base case for the recursion is when the sub-polygon has fewer than 3 vertices (i.e., `j < i + 2`). In this case, no triangles can be formed, so the score is 0. The final answer is obtained by calling `solve(0, n-1)`.

```java
class Solution {
    public int minScoreTriangulation(int[] values) {
        return solve(values, 0, values.length - 1);
    }

    private int solve(int[] values, int i, int j) {
        // Base case: if there are less than 3 vertices, no triangle can be formed.
        if (j < i + 2) {
            return 0;
        }

        int minScore = Integer.MAX_VALUE;
        // k is the middle vertex of the triangle (i, k, j)
        for (int k = i + 1; k < j; k++) {
            int currentScore = solve(values, i, k) + solve(values, k, j) + values[i] * values[k] * values[j];
            minScore = Math.min(minScore, currentScore);
        }
        return minScore;
    }
}
```
### Algorithm
- Define a recursive function `solve(values, i, j)` that computes the minimum triangulation score for the polygon formed by vertices `values[i], ..., values[j]`.
- The base case for the recursion is when there are fewer than 3 vertices (i.e., `j < i + 2`). In this scenario, no triangles can be formed, so the function returns 0.
- Initialize a variable `minScore` to a very large value (e.g., `Integer.MAX_VALUE`).
- Iterate through all possible intermediate vertices `k` from `i + 1` to `j - 1`. Each `k` forms a triangle `(i, k, j)`.
- For each `k`, the total score is the sum of the score of the triangle `(i, k, j)` and the scores of the resulting sub-polygons. This is calculated recursively as `solve(i, k) + solve(k, j) + values[i] * values[k] * values[j]`.
- Update `minScore` with the minimum value found across all choices of `k`.
- Return `minScore`.
- The main function calls `solve(values, 0, n-1)` to get the final answer, where `n` is the number of vertices.

## Memoization (Top-Down Dynamic Programming)
This approach improves upon the plain recursion by caching the results of subproblems to avoid re-computation. We use a 2D array, say `memo`, to store the computed minimum scores for sub-polygons. `memo[i][j]` will store the result of `solve(i, j)`. Before computing the result for a subproblem `(i, j)`, we first check if `memo[i][j]` has already been computed. If it has, we return the stored value. Otherwise, we compute it, store it in `memo[i][j]`, and then return it.
**Time:** O(n^3). There are O(n^2) unique subproblems `(i, j)`. Each subproblem takes O(n) time to compute (due to the loop over `k`). Since each subproblem is solved only once, the total time is O(n^2 * n) = O(n^3). · **Space:** O(n^2) for the memoization table, plus O(n) for the recursion stack depth. The total space is dominated by the table, so it's O(n^2).
**Pros:** Much more efficient than plain recursion, avoiding redundant calculations.; Guaranteed to pass within the time limits for `n <= 50`.; Often more intuitive to write than the bottom-up approach if one thinks recursively.
**Cons:** Can lead to a `StackOverflowError` for very large `n` (though not an issue for `n <= 50`).; Has the overhead of recursive function calls, which can be slightly slower than an iterative approach.
### Explanation
This is a standard optimization for recursive solutions with overlapping subproblems, also known as top-down dynamic programming. We introduce a 2D array `memo[n][n]` initialized with a value indicating that the state has not been computed (e.g., 0, since scores are guaranteed to be positive).

The recursive function `solve(i, j)` is modified as follows:
1. At the beginning of the function, check if `memo[i][j]` is already computed. If so, return `memo[i][j]`.
2. If not, proceed with the calculation as in the recursive approach.
3. Before returning the calculated `minScore`, store it in `memo[i][j]`.

```java
class Solution {
    private int[][] memo;
    private int[] values;

    public int minScoreTriangulation(int[] values) {
        this.values = values;
        int n = values.length;
        this.memo = new int[n][n];
        return solve(0, n - 1);
    }

    private int solve(int i, int j) {
        // Base case: if there are less than 3 vertices, no triangle can be formed.
        if (j < i + 2) {
            return 0;
        }
        // Check if the result is already memoized.
        if (memo[i][j] != 0) {
            return memo[i][j];
        }

        int minScore = Integer.MAX_VALUE;
        // k is the middle vertex of the triangle (i, k, j)
        for (int k = i + 1; k < j; k++) {
            int currentScore = solve(i, k) + solve(k, j) + values[i] * values[k] * values[j];
            minScore = Math.min(minScore, currentScore);
        }
        
        // Memoize the result before returning.
        memo[i][j] = minScore;
        return minScore;
    }
}
```
### Algorithm
- Initialize an `n x n` memoization table `memo` with a sentinel value (e.g., 0, since scores are positive).
- Define a recursive function `solve(i, j)`.
- Base case: if `j < i + 2`, return 0.
- Memoization check: if `memo[i][j]` is not the sentinel value, it means the result for this subproblem has been computed, so return `memo[i][j]`.
- If the result is not memoized, initialize `minScore` to a large value.
- Iterate `k` from `i + 1` to `j - 1`.
- For each `k`, recursively call `solve` to get the score: `solve(i, k) + solve(k, j) + values[i] * values[k] * values[j]`.
- Update `minScore` with the minimum score found.
- Store the computed `minScore` in `memo[i][j]` before returning it.
- The initial call is `solve(0, n-1)`.

## Tabulation (Bottom-Up Dynamic Programming)
This is an iterative approach that systematically solves all subproblems, starting from the smallest ones and building up to the final solution. This is also known as bottom-up dynamic programming. We use a 2D DP table, `dp[n][n]`, where `dp[i][j]` stores the minimum triangulation score for the polygon with vertices from `i` to `j`. We fill this table by iterating over the length of the sub-polygon, ensuring that when we compute `dp[i][j]`, the values for smaller subproblems (`dp[i][k]` and `dp[k][j]`) are already available.
**Time:** O(n^3). There are three nested loops. The outer loop for `gap` runs O(n) times. The middle loop for `i` runs O(n) times. The inner loop for `k` also runs O(n) times. This gives a total time complexity of O(n^3). · **Space:** O(n^2), for the 2D DP table.
**Pros:** Avoids recursion overhead and the risk of stack overflow, making it very robust.; Generally the most performant solution in practice due to better memory access patterns and no function call overhead.; It's the most efficient standard approach for this problem.
**Cons:** Can be slightly less intuitive to formulate and implement compared to the top-down recursive approach.
### Explanation
We iterate over the 'gap' or length of the sub-polygon, from 2 up to `n-1`. The gap `g` represents `j - i`.
- The outer loop iterates `g` from 2 to `n-1`.
- The inner loop iterates through the starting vertex `i` from 0 to `n-1-g`. The ending vertex `j` is `i + g`.
- For each pair `(i, j)`, we calculate `dp[i][j]` using the same recurrence relation as before:
  `dp[i][j] = min_{i < k < j} (dp[i][k] + dp[k][j] + values[i] * values[j] * values[k])`
- The base cases `dp[i][i+1]` (gap=1) are implicitly 0, as our `dp` table is initialized to zeros and the loops for `g` start from 2.
- The final answer is stored in `dp[0][n-1]`.

```java
class Solution {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];

        // gap is the length of the sub-polygon chain (j - i)
        for (int gap = 2; gap < n; gap++) {
            for (int i = 0; i < n - gap; i++) {
                int j = i + gap;
                dp[i][j] = Integer.MAX_VALUE;
                // k is the splitting vertex
                for (int k = i + 1; k < j; k++) {
                    int score = dp[i][k] + dp[k][j] + values[i] * values[j] * values[k];
                    dp[i][j] = Math.min(dp[i][j], score);
                }
            }
        }
        return dp[0][n - 1];
    }
}
```
### Algorithm
- Create an `n x n` DP table, `dp`, and initialize it with 0s.
- Iterate over the `gap` from 2 to `n-1`. The `gap` represents the length of the polygon chain (`j - i`).
- For each `gap`, iterate over the starting index `i` from 0 up to `n - 1 - gap`.
- Calculate the ending index `j = i + gap`.
- Initialize `dp[i][j]` to a very large value.
- Iterate through all possible splitting vertices `k` from `i + 1` to `j - 1`.
- For each `k`, calculate the score for the current split using previously computed values: `dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]`.
- Update `dp[i][j]` with the minimum score found among all `k`.
- After the loops complete, `dp[0][n-1]` will hold the minimum score for the entire polygon. Return this value.

# Solutions
### Java

```java
class Solution {
private
  int n;
private
  int[] values;
private
  Integer[][] f;
public
  int minScoreTriangulation(int[] values) {
    n = values.length;
    this.values = values;
    f = new Integer[n][n];
    return dfs(0, n - 1);
  }
private
  int dfs(int i, int j) {
    if (i + 1 == j) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    int ans = 1 << 30;
    for (int k = i + 1; k < j; ++k) {
      ans = Math.min(ans,
                     dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j]);
    }
    return f[i][j] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minScoreTriangulation(vector<int> &values) {
    int n = values.size();
    int f[n][n];
    memset(f, 0, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (i + 1 == j) {
        return 0;
      }
      if (f[i][j]) {
        return f[i][j];
      }
      int ans = 1 << 30;
      for (int k = i + 1; k < j; ++k) {
        ans =
            min(ans, dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j]);
      }
      return f[i][j] = ans;
    };
    return dfs(0, n - 1);
  }
};

```

### Python

```python
class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int: @ cache def dfs(i: int, j: int) -> int: if i + 1 == j: return 0 return min(dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j] for k in range(i + 1, j)) return dfs(0, len(values) - 1)

```