Minimum Score Triangulation of Polygon

main.md

Question

Approach

I treat the polygon as an interval [i, j] of vertices. If I want to triangulate that section, I pick a third vertex k between i and j to form triangle (i, k, j). The cost is values[i] * values[k] * values[j] + dp[i][k] + dp[k][j]. I compute the minimum across all choices of k.

Implementation

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        n = len(values)
        dp = [[0] * n for _ in range(n)]
        
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = float('inf')
                for k in range(i + 1, j):
                    dp[i][j] = min(dp[i][j],
                                   dp[i][k] + dp[k][j] + values[i] * values[k] * values[j])
        
        return dp[0][n - 1]

Complexities

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