- 标签:数组、动态规划
- 难度:中等
描述:有一个凸的
现在要将
要求:返回多边形进行三角剖分可以得到的最低分。
说明:
-
$n == values.length$ 。 -
$3 \le n \le 50$ 。 -
$1 \le values[i] \le 100$ 。
示例:
- 示例 1:
输入:values = [1,2,3]
输出:6
解释:多边形已经三角化,唯一三角形的分数为 6。
- 示例 2:
输入:values = [3,7,4,5]
输出:144
解释:有两种三角剖分,可能得分分别为:3*7*5 + 4*5*7 = 245,或 3*4*5 + 3*4*7 = 144。最低分数为 144。
对于
- 顶点
$0 \sim k$ 组成的凸多边形。 - 顶点
$0$ 、$k$、$n - 1$ 组成的三角形。 - 顶点
$k \sim n - 1$ 组成的凸多边形。
对于顶点
而对于顶点
具体做法如下:
按照区间长度进行阶段划分。
定义状态
对于区间
- 默认情况下,所有区间
$[i, j]$ 的最小分数为无穷大。 - 当区间
$[i, j]$ 长度小于$3$ 时,无法进行三角剖分,其最小分数为$0$ 。 - 当区间
$[i, j]$ 长度等于$3$ 时,其三角剖分的最小分数为$values[i] * values[i + 1] * values[i + 2]$ 。
根据我们之前定义的状态,$dp[i][j]$ 表示为:区间
class Solution:
def minScoreTriangulation(self, values: List[int]) -> int:
size = len(values)
dp = [[float('inf') for _ in range(size)] for _ in range(size)]
for l in range(1, size + 1):
for i in range(size):
j = i + l - 1
if j >= size:
break
if l < 3:
dp[i][j] = 0
elif l == 3:
dp[i][j] = values[i] * values[i + 1] * values[i + 2]
else:
for k in range(i + 1, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k])
return dp[0][size - 1]
-
时间复杂度:$O(n^3)$,其中
$n$ 为顶点个数。 - 空间复杂度:$O(n^2)$。