Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1111. Minimum Score Triangulation of Polygon

My accepted Python solution to LeetCode problem 1111, Minimum Score Triangulation of Polygon, running in 35ms.

  • Difficulty: Medium
  • Python
  • Runtime 35ms
  • Memory 17.4MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 35ms, memory 17.4MB, accepted 2026-01-02.

python
class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        n = len(values)
        # dp[i][j] = minimum score to triangulate polygon from vertex i to j
        dp = [[0] * n for _ in range(n)]
        
        # Fill for increasing length of polygon
        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):
                    score = values[i] * values[k] * values[j] + dp[i][k] + dp[k][j]
                    dp[i][j] = min(dp[i][j], score)
        
        return dp[0][n-1]

Source