Leetcode Problem 1039. Minimum Score Triangulation of Polygon

1039. Minimum Score Triangulation of Polygon

Leetcode Solutions

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.
Fill the dp array with default values (e.g., -1 or INT_MAX) to indicate that the subproblem has not been solved yet.
Define a recursive function minScore that takes the indices i and j as arguments, representing the vertices of the sub-polygon.
If i + 1 == j, there are only two vertices, and no triangle can be formed, so return 0.
If dp[i][j] is not the default value, return dp[i][j] as the subproblem has already been solved.
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).
Update dp[i][j] with the minimum score found.
Return dp[i][j] as the minimum score for the sub-polygon defined by vertices i and j.
Call the recursive function with the full polygon (0, n-1) to get the minimum score for the entire polygon.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen