Leetcode Problem 1039. Minimum Score Triangulation of Polygon

1039. Minimum Score Triangulation of Polygon

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a 2D array dp with dimensions n x n to store the minimum score for sub-polygons, where n is the number of vertices in the polygon.
  2. Fill the dp array with default values (e.g., -1 or INT_MAX) to indicate that the subproblem has not been solved yet.
  3. Define a recursive function minScore that takes the indices i and j as arguments, representing the vertices of the sub-polygon.
  4. If i + 1 == j, there are only two vertices, and no triangle can be formed, so return 0.
  5. If dp[i][j] is not the default value, return dp[i][j] as the subproblem has already been solved.
  6. Iterate over all possible vertices k between i and j and calculate the score for the triangle formed by vertices i, j, and k, and add the minimum scores of the two sub-polygons formed by the diagonal (i, k) and (k, j).
  7. Update dp[i][j] with the minimum score found.
  8. Return dp[i][j] as the minimum score for the sub-polygon defined by vertices i and j.
  9. Call the recursive function with the full polygon (0, n-1) to get the minimum score for the entire polygon.
UML Thumbnail

Recursive Approach with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...