1039. Minimum Score Triangulation of Polygon LeetCode Solution

In this guide, you will get 1039. Minimum Score Triangulation of Polygon LeetCode Solution with the best time and space complexity. The solution to Minimum Score Triangulation of Polygon problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Score Triangulation of Polygon solution in C++
Minimum Score Triangulation of Polygon solution in Java
Minimum Score Triangulation of Polygon solution in Python
Additional Resources

1039. Minimum Score Triangulation of Polygon LeetCode Solution image

Problem Statement of Minimum Score Triangulation of Polygon

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:

Input: values = [1,2,3]
Output: 6
Explanation: The polygon is already triangulated, and the score of the only triangle is 6.

Example 2:

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:

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

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

1039. Minimum Score Triangulation of Polygon LeetCode Solution in C++

class Solution {
 public:
  int minScoreTriangulation(vector<int>& values) {
    const int n = values.size();
    vector<vector<int>> dp(n, vector<int>(n));

    for (int j = 2; j < n; ++j)
      for (int i = j - 2; i >= 0; --i) {
        dp[i][j] = INT_MAX;
        for (int k = i + 1; k < j; ++k)
          dp[i][j] =
              min(dp[i][j],
                  dp[i][k] + values[i] * values[k] * values[j] + dp[k][j]);
      }

    return dp[0][n - 1];
  }
};
/* code provided by PROGIEZ */

1039. Minimum Score Triangulation of Polygon LeetCode Solution in Java

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

    for (int j = 2; j < n; ++j)
      for (int i = j - 2; i >= 0; --i) {
        dp[i][j] = Integer.MAX_VALUE;
        for (int k = i + 1; k < j; ++k)
          dp[i][j] = Math.min(dp[i][j], dp[i][k] + values[i] * values[k] * values[j] + dp[k][j]);
      }

    return dp[0][n - 1];
  }
}
// code provided by PROGIEZ

1039. Minimum Score Triangulation of Polygon LeetCode Solution in Python

class Solution:
  def minScoreTriangulation(self, values: list[int]) -> int:
    n = len(values)
    dp = [[0] * n for _ in range(n)]

    for j in range(2, n):
      for i in range(j - 2, -1, -1):
        dp[i][j] = math.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]
 # code by PROGIEZ