Minimum Score Triangulation of Polygon Using Backtracking

minimum_score_triangulation_of_polygon.py

class Solution:
    def minScore(self, values: List[int], n, used, usedctr) -> int:
        if usedctr == n - 2:
            return 0
        if used in self.cache:
            return self.cache[used]
        minScore = float('inf')
        for i in range(n):
            if not used & (1 << i + 1):
                l = (n + i - 1) % n
                r = (i + 1) % n
                while used & (1 << l + 1):
                    l = (n + l - 1) % n
                while used & (1 << r + 1):
                    r = (r + 1) % n
                used |= 1 << i + 1
                currScore = values[l] * values[i] * values[r] + self.minScore(values, n, used, usedctr + 1)
                used &= ~(1 << i + 1)
                minScore = min(minScore, currScore)
        self.cache[used] = minScore
        return minScore
    
    def minScoreTriangulation(self, values: List[int]) -> int:
        n = len(values)
        self.cache = {}
        used = 0
        return self.minScore(values, n, used, 0)