lc1039. 多边形三角剖分的最低得分

题目链接:1039. 多边形三角剖分的最低得分

题解

区间 DP,假设 dp[i][j]dp[i][j] 为从 i 到 j 进行三角剖分后最低分。枚举 i 到 j 中间存在一个点 k,使多边形变成三部分:ik, kj 以及 ijk 三角形的多边形,取最小的就是 ij 的最低分。

用 DFS 来写比直接写出递推公式简单一些。

看了标签和官方题解才写出来!

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def minScoreTriangulation(self, values: List[int]) -> int:
mp = {}
def dp(i, j):
if j - i < 2:
return 0
if j - i == 2:
return values[i]*values[i+1]*values[j]
if (i,j) in mp:
return mp[(i,j)]
ans = 1e9
for k in range(i+1, j):
tmp = dp(i, k) + dp(k, j) + values[i]*values[k]*values[j]
ans = min(tmp, ans)
mp[(i,j)] = ans
return ans

return dp(0, len(values)-1)

错误贪心

枚举一个点做为顶点,往其他点连线将平面且分成 n-2 个三角形,样例第三个都过不了……

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def minScoreTriangulation(self, values: List[int]) -> int:
n = len(values)
aa = values + values
ans = 1e9+7
for i in range(n):
tmp = 0
for j in range(1, n-1):
tmp += aa[i] * aa[i+j] * aa[i+j+1]
print(tmp)
ans = min(tmp, ans)
return ans

lc1039. 多边形三角剖分的最低得分

https://blog.xiang578.com/problem/lc1039.html

作者

Ryen Xiang

发布于

2023-04-02

更新于

2024-08-05

许可协议


网络回响

评论