难度：★★★★☆
类型：几何，数组
方法：动态规划

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。

假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

返回多边形进行三角剖分后可以得到的最低分。

示例 1：

输入：[1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。

示例 2：

输入：[3,7,4,5]
输出：144
解释：有两种三角剖分，可能得分分别为：375 + 457 = 245，或 345 + 347 = 144。最低分数为 144。

示例 3：

输入：[1,3,1,4,1,5]
输出：13
解释：最低分数三角剖分的得分情况为 113 + 114 + 115 + 111 = 13。

提示：

3 <= A.length <= 50
1 <= A[i] <= 100

解答

我们先来理解一下什么是三角剖分。首先，多边形每个顶点都是一个数字，三个顶点组成一个三角形，这个三角形的分数就是三个顶点的乘积，多边形有很多个顶点，需要把这些顶点连线，这些线不能交叉，而且所有顶点都需要作为至少一个连线的端点。这样多边形就变成了只由三角形组成的一个状态。多边形的三角剖分就是拆好的三角形的分数之和。

我们用动态规划解决。

【数组定义】

多边形各个顶点是按顺序编了号的，一个n边形各个顶点是0,1,2，...，n-1。我们从中选两个顶点i和j，且j>i+1，这样从编号i到j的所有点就可以组成新的多边形了（包括三角形）。

定义数组dp，维度为n×n，dp[i][j]表示由i，i+1,i+2,...j-1,j这些点组成的多边形的三角剖分最小值。

【初始状态】

因为最后要求最小值，我们就把dp数组中每个点填充为正无穷。

【递推公式】

这里要解决dp[i][j]怎么求的问题。对于从i到j的所有点（不包括i和j），任选一点k（i<k<j），我们实际上就把从点i到点j的多边形划分成了三个小块，分别是从i到k的小多边形，从k到j的小多边形以及三角形ikj。这时，整体的分数就很好计算了：

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

根据题意，我们需要研究从i与j之间所有点k的情况，取其中最小的剖分数，作为dp[i][j]的值。

【返回值】

根据dp数组的含义，我们需要在遍历完成后返回dp[0][-1]即可。

【注意事项】

遍历顺序需要留意，因为我们在递推公式中提到，dp[k][j]和dp[i][k]是要先于dp[i][j]计算出来的，所以j正向遍历时，为了避免找不到缓存结果dp[k][j]和dp[i][k]的尴尬情况，我们需要将i逆序遍历。保证遍历过程以及dp数组更新的连续性。

最后得到dp数组实际上只有右上角半个三角形。

from typing import List


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

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析