Minimum Score Triangulation of Polygon
You have a convex n-sided polygon where each vertex has an integer value. These values are given in an integer array values, where values[i] is the value of the ith vertex.
The score of a triangulation is the sum of the scores of all its triangles. The score of a triangle is the product of the values of its three vertices.
Return the minimum score of a triangulation of the given polygon.
Examples
Input: [1,2,3]
Output: 6
Input: [3,7,4,5]
Output: 144
Hints
**Hint 1**: Use dynamic programming to break the problem into smaller subproblems. Consider the polygon as a sequence of vertices and define `dp[i][j]` as the minimum score to triangulate the polygon from vertex `i` to vertex `j`.
**Hint 2**: For each subproblem `dp[i][j]`, iterate over all possible intermediate vertices `k` (where `i < k < j`) to split the polygon into two parts: a triangle `(i, k, j)` and the remaining polygon `(i, ..., k)` and `(k, ..., j)`. Combine their scores to find the minimum.
**Hint 3**: Optimize the DP by noting that the polygon is convex, so the subproblems are independent. The base case is when `j - i <= 2` (a triangle or a line), where the score is `0` (no further triangulation needed). Use memoization or a bottom-up approach to fill the DP table efficiently.
Related Problems
Minimum Score Triangulation of Polygon
You have a convex `n`-sided polygon where each vertex has an integer value. These values are given in an integer array `values`, where `values[i]` is the value of the `i`th vertex.