leetcode1039

 1 class Solution:
 2     def __init__(self):
 3         self.dic = {}
 4 
 5     def minScoreTriangulation(self, A: ‘List[int]‘) -> int:
 6         tp = tuple(A)
 7         if tp in self.dic.keys():
 8             return self.dic[tp]
 9         else:
10             n = len(A)
11             if n == 3:
12                 r = A[0] * A[1] * A[2]
13                 self.dic.update({tuple(A):r})
14                 return r
15             result = sys.maxsize
16             cur = 0
17             for i in range(n//2):#n>3
18                 if i > 0:
19                     temp = A.pop(0)
20                     A.append(temp)
21                 for j in range(2,n-1):
22                     part1 = A[0:j+1]
23                     part2 = A[j:] + A[0:1]
24                     tuple1 = tuple(part1)
25                     tuple2 = tuple(part2)
26                     p1 = self.minScoreTriangulation(part1)
27                     p2 = self.minScoreTriangulation(part2)
28                     cur = p1 + p2
29                     result = min(result,cur)
30             self.dic.update({tp:result})
31             return result