Loading problem...
You are given a convex polygon with n vertices, where each vertex is assigned an integer weight. The vertices are arranged in clockwise order, and you are provided an integer array values where values[i] represents the weight of the i-th vertex.
Your task is to triangulate the polygon—that is, decompose it into a set of non-overlapping triangles such that every triangle's vertices are also vertices of the original polygon. A convex polygon with n vertices can always be divided into exactly n - 2 triangles through triangulation.
Each triangle formed during the triangulation has an associated cost, which is calculated as the product of the weights of its three vertices. The total triangulation cost is the sum of the costs of all n - 2 triangles.
Your goal is to determine the minimum possible total triangulation cost that can be achieved through any valid triangulation of the polygon.
A triangulation splits a polygon into triangles by drawing non-intersecting diagonals between vertices. For a convex polygon:
Different ways of drawing these diagonals lead to different triangulations, each potentially having a different total cost. Your task is to find the arrangement that minimizes the total cost.
values = [1,2,3]6A triangle (3 vertices) is already a triangulation with exactly 1 triangle. The cost is simply the product of all three vertex weights: 1 × 2 × 3 = 6. There's only one possible triangulation for a triangle.
values = [3,7,4,5]144For a quadrilateral (4 vertices), there are exactly two possible triangulations: • Triangulation 1: Draw diagonal from vertex 0 to vertex 2. This creates triangles (3,7,4) and (3,4,5) with costs 3×7×4 = 84 and 3×4×5 = 60. Total = 144. • Triangulation 2: Draw diagonal from vertex 1 to vertex 3. This creates triangles (3,7,5) and (7,4,5) with costs 3×7×5 = 105 and 7×4×5 = 140. Total = 245. The minimum cost is 144.
values = [1,3,1,4,1,5]13This hexagon has 6 vertices, requiring 4 triangles. The optimal triangulation uses vertex 0 (value=1) in multiple triangles to minimize costs. One optimal arrangement forms triangles: (1,1,3), (1,1,4), (1,1,5), and (1,1,1) with costs 3, 4, 5, and 1 respectively. Total minimum cost = 3 + 4 + 5 + 1 = 13.
Constraints