GivenN, consider a convexN-sided polygon with vertices labelledA[0], A[i], ..., A[N-1] in clockwise order.
Suppose you triangulate the polygon intoN-2triangles. For each triangle, the value of that triangle is theproduct of the labels of the vertices, and the_total score_of the triangulation is the sum of these values over allN-2triangles in the triangulation.
Return the smallest possible total score that you can achieve with some triangulation of the polygon.
Example 1:
Input:
[1,2,3]
Output:
6
Explanation:
The polygon is already triangulated, and the score of the only triangle is 6.
Example 2:
Input:
[3,7,4,5]
Output:
144
Explanation:
There are two triangulations, with possible scores: 3*7*5 + 4*5*7 = 245, or 3*4*5 + 3*4*7 = 144. The minimum score is 144.
Example 3:
Input:
[1,3,1,4,1,5]
Output:
13
Explanation:
The minimum score triangulation has score 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.
class Solution:
def minScoreTriangulation(self, A: List[int]) -> int:
n = len(A)
dp = [[float('inf')] *n for _ in range(n)]
def dfs(i,j):
if j - i + 1 < 3: #初始化为最大，但是前三个数要初始为0
return 0
if dp[i][j] != float('inf'):
return dp[i][j]
res = float('inf')
for k in range(i+1,j): #注意此处范围，i.j内不含i,j
res = min(res, dfs(i,k) + A[i]*A[j]*A[k] + dfs(k,j))
dp[i][j] = res
return res
return dfs(0,n-1)
bottom up DP
遍历长度d>[2-n] ,left [0- n-d]
从小长度到大长度。 其他遍历法要倒序
class Solution:
def minScoreTriangulation(self, A: List[int]) -> int:
n = len(A)
dp = [[0] *n for _ in range(n)]
for l in range(2,n):
for left in range(n-l):
right = left + l
dp[left][right] = float('inf')
for k in range(left+1,right): #注意此处范围，i.j内不含i,j
dp[left][right] = min(dp[left][right], dp[left][k] + A[left]*A[right]*A[k] + dp[k][right])
return dp[0][n-1]
