1039. Minimum Score Triangulation of Polygon (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        # dfs without memo TLE
        # if len(values) < 3:
        #     return 0
        # return min([self.minScoreTriangulation(values[ : i + 1]) + 
        #             self.minScoreTriangulation(values[i : ]) + 
        #             values[0] * values[-1] * values[i] 
        #             for i in range(1, len(values) - 1)])
        
        # dfs with memo AC
        def dfs(i, j):
            if (i, j) not in seen:
                seen[i, j] = min([dfs(i, k) + dfs(k, j) + values[i] * values[j] * values[k] for k in range(i + 1, j)] or [0])
            return seen[i, j]
        seen = {} 
        return dfs(0, len(values) - 1)
    
        # lru_cache trick
        @lru_cache(None)
        def dfs(i, j):
            return min([dfs(i, k) + dfs(k, j) + values[i] * values[j] * values[k] for k in range(i + 1, j)] or [0])
        return dfs(0, len(values) - 1)