Minimum Score Triangulation of Polygon LeetCode solution in Python

1
class Solution:
2
    def minScoreTriangulation(self, values: List[int]) -> int:
3

4
        n = len(values)
5

6
        c = [[0 for _ in range(n)] for _ in range(n)]
7

8
        for L in range(2, n):
9

10
            for i in range(1, n - L + 1):
11

12
                j = i + L - 1
13

14
                c[i][j] = float("inf")
15

16
                for k in range(i, j):
17

18
                    q = c[i][k] + c[k + 1][j] + (values[i - 1] * values[k] * values[j])
19

20
                    if c[i][j] > q:
21
                        c[i][j] = q
22

23
        return c[1][n - 1]