[leetcode] 1039. Minimum Score Triangulation of Polygon

Description

Given N, consider a convex N-sided polygon with vertices labelled A[0], A[i], …, A[N-1] in clockwise order.

Suppose you triangulate the polygon into N-2 triangles. For each triangle, the value of that triangle is the product of the labels of the vertices, and the total score of the triangulation is the sum of these values over all N-2 triangles 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: 6Explanation: The polygon is already triangulated, and the score of the only triangle is 6.

Example 2:

Input: [3,7,4,5]Output: 144Explanation: 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: 13Explanation: The minimum score triangulation has score 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.

Note:

3 <= A.length <= 501 <= A[i] <= 100

分析

题目的意思是：给定一个数组，代表多边形的每个节点的值，然后划分成若干个三角形，对每个三角形的三个顶点进行乘积，最后求和。求划分的最小值，划分的线不交叉。

首先可以选择划分的点把数组划分成左右两部分，然后分别划分三角形，这样递归下去，找乘积最小的划分。另一种是使用dp方程,dp[i][j]表示数组中的A[i:j]构成的最小乘积和，我们在A[i:j]之间遍历找最小划分点k，然后会分成两个子问题dp[i][k] dp[k][j] A[i]*A[j]*A[k]，这样就能求出最终得推公式了：

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+A[i]*A[k]*A[j])

i从0开始，j至少从2开始哈，不然构成不了三角形，哈哈哈。 dp从前往后计算的时候，对于为0的情况，表明当前的dp还未计算，这种情况要分开讨论

dp[i][j]=dp[i][k]+dp[k][j]+A[i]*A[k]*A[j]

直接赋值就行了，由于是从前往后计算，范围是慢慢扩大的，所以dp[i][k],dp[k][j]肯定是被计算过了的。我把例3的dp数组数出来，有兴趣的可以手动算一遍

[[0, 0, 3, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]][[0, 0, 3, 0, 0, 0], [0, 0, 0, 12, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]][[0, 0, 3, 0, 0, 0], [0, 0, 0, 12, 0, 0], [0, 0, 0, 0, 4, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]][[0, 0, 3, 0, 0, 0], [0, 0, 0, 12, 0, 0], [0, 0, 0, 0, 4, 0], [0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]][[0, 0, 3, 7, 0, 0], [0, 0, 0, 12, 0, 0], [0, 0, 0, 0, 4, 0], [0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]][[0, 0, 3, 7, 0, 0], [0, 0, 0, 12, 7, 0], [0, 0, 0, 0, 4, 0], [0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]][[0, 0, 3, 7, 0, 0], [0, 0, 0, 12, 7, 0], [0, 0, 0, 0, 4, 9], [0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]][[0, 0, 3, 7, 8, 0], [0, 0, 0, 12, 7, 0], [0, 0, 0, 0, 4, 9], [0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]][[0, 0, 3, 7, 8, 0], [0, 0, 0, 12, 7, 22], [0, 0, 0, 0, 4, 9], [0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]][[0, 0, 3, 7, 8, 13], [0, 0, 0, 12, 7, 22], [0, 0, 0, 0, 4, 9], [0, 0, 0, 0, 0, 20], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]

代码

class Solution: def minScoreTriangulation(self, A: List[int]) -> int: n=len(A) dp=[[0]*n for i in range(n)] for d in range(2,n): for i in range(n-d): j=i+d for k in range(i+1,j): if(dp[i][j]==0): dp[i][j]=dp[i][k]+dp[k][j]+A[i]*A[k]*A[j] else: dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+A[i]*A[k]*A[j]) return dp[0][n-1]

代码二

class Solution: def minScoreTriangulation(self, A): n=len(A) dp=[[0]*n for i in range(n)] for d in range(2,n): for i in range(n-d): j=i+d for k in range(i+1,j): if(dp[i][j]==0): dp[i][j]=dp[i][k]+dp[k][j]+A[i]*A[k]*A[j] else: dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+A[i]*A[k]*A[j]) print(dp) return dp[0][n-1]if __name__ == "__main__": solution=Solution() arr=[3,7,4,5] res=solution.minScoreTriangulation(arr) print(res)

参考文献

​​[LeetCode] [C++/Python] O(n^3) DP explanation + diagrams​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。