Minimum Score Triangulation of Polygon 🌟

Medium

---

📖 Problem Description

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 i-th vertex in clockwise order.

Polygon triangulation is a process where you divide a polygon into a set of triangles, such that:

• Each triangle’s vertices are also vertices of the original polygon.
• No other shapes besides triangles are allowed.
• This process will always result in n - 2 triangles.

For each triangle, the weight is the product of the values at its vertices.
The total score of the triangulation is the sum of weights over all n - 2 triangles.

🔹 Your task: Return the minimum possible score achievable for 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
1 * 2 * 3 = 6.

---

Example 2:

Input:
values = [3,7,4,5]
Output:
144

Explanation:
There are two triangulations:

• (3 * 7 * 5) + (4 * 5 * 7) = 245
• (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:
One optimal 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

---

📊 Extra Info

• Seen in interviews: 1/5
• Accepted: 65,602 / 108.2K
• Acceptance Rate: 60.7%

---

🔑 Topics

• Dynamic Programming
• Geometry

---

— Written by Saurabh Patil • B.Tech CSE • Software Developer