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

尝试使用字典记录已经计算过的项，但是执行效率没有明显的改善。

这道题目想要提升效率，需要使用动态规划的思想。我没有思路。

动态规划最核心的是寻找递归公式，也就是把题目中隐含的数学关系用一个式子写出来。

这类问题对于我这样数学不好的人来说，的确比较困难。

以我的水平，能写出“超时”的解就可以了。谁让咱技能树没有点数学这个天赋呢。

下面提供一个高大上的实现：

 1 from functools import lru_cache
 2 
 3 class Solution:
 4     def minScoreTriangulation(self, A):
 5         @lru_cache(None)
 6         def dp(i, j):
 7             if j - i + 1 < 3:
 8                 return 0
 9             return min(A[i]*A[j]*A[k] + dp(i, k) + dp(k, j) for k in range(i + 1, j))
10         return dp(0, len(A) - 1)

参考：https://leetcode.com/problems/minimum-score-triangulation-of-polygon/discuss/286754/C%2B%2BPython-O(n3)-DP-explanation-%2B-diagrams