# LeetCode 1039: Minimum Score Triangulation of Polygon

## Problem Restatement

We have a convex polygon with `n` vertices labeled `0` to `n - 1`.

Each vertex has a value given in `values[i]`.

We triangulate the polygon into `n - 2` triangles. For each triangle with vertices `i`, `j`, `k`, the score is `values[i] * values[j] * values[k]`.

We need to return the minimum total score over all possible triangulations.

The official constraints state that `n == values.length`, `3 <= n <= 50`, and `1 <= values[i] <= 100`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `values` of polygon vertex values |
| Output | Minimum total triangulation score |

Function shape:

```python
def minScoreTriangulation(values: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
values = [1, 2, 3]
```

Only one triangulation: triangle `(0, 1, 2)`. Score = `1 * 2 * 3 = 6`.

Answer:

```python
6
```

Example 2:

```python
values = [3, 7, 4, 5]
```

Two triangulations:
- Diagonals `(0,2)`: triangles `(0,1,2)` and `(0,2,3)`. Score = `84 + 60 = 144`.
- Diagonals `(1,3)`: triangles `(0,1,3)` and `(1,2,3)`. Score = `105 + 140 = 245`.

Answer:

```python
144
```

## Key Insight

This is an interval DP problem.

Fix vertex `0` (or any vertex). Every triangle in the triangulation includes exactly two boundary vertices of the current sub-polygon. The third vertex splits the problem into two subproblems.

Let `dp[i][j]` = minimum score to triangulate the sub-polygon with vertices `i, i+1, ..., j`.

For each possible "apex" vertex `k` between `i` and `j`:

```python
dp[i][j] = min over k in (i+1, j-1):
    dp[i][k] + values[i] * values[k] * values[j] + dp[k][j]
```

## Correctness

Fixing edge `(i, j)` and trying all apex vertices `k` between them covers every valid triangle that uses edge `(i, j)`. The recurrence combines the two sub-polygons on either side of the diagonal `(i, k)` and `(k, j)`.

Base case: any sub-polygon with fewer than 3 vertices has score 0.

## Edge Cases

- Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
- Confirm the iteration order matches the recurrence dependencies.
- For optimization DP, separate impossible states from valid states with value `0`.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^3)` | Three nested loops |
| Space | `O(n^2)` | DP table |

## Common Pitfalls

- Do not overwrite a state before all transitions that still need the old value have used it.
- Use the problem constraints to choose between full tables and compressed state.

## Implementation

```python
class Solution:
    def minScoreTriangulation(self, values: list[int]) -> int:
        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):
                    dp[i][j] = min(dp[i][j],
                        dp[i][k] + values[i] * values[k] * values[j] + dp[k][j])

        return dp[0][n - 1]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minScoreTriangulation([1, 2, 3]) == 6
    assert s.minScoreTriangulation([3, 7, 4, 5]) == 144
    assert s.minScoreTriangulation([1, 3, 1, 4, 1, 5]) == 13

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Triangle | `6` | Only one triangulation |
| Quadrilateral | `144` | Better diagonal choice |
| 6-gon with 1s | `13` | Small vertex values minimize products |