1039.多边形三角剖分的最低得分:记忆化搜索(深度优先搜索)
【LetMeFly】1039.多边形三角剖分的最低得分:记忆化搜索(深度优先搜索)
力扣题目链接:https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/
你有一个凸的 n
边形,其每个顶点都有一个整数值。给定一个整数数组 values
,其中 values[i]
是第 i
个顶点的值(即 顺时针顺序 )。
假设将多边形 剖分 为 n - 2
个三角形。对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 n - 2
个三角形的值之和。
返回 多边形进行三角剖分后可以得到的最低分 。
示例 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。
示例 3:
输入:values = [1,3,1,4,1,5] 输出:13 解释:最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
提示:
n == values.length
3 <= n <= 50
1 <= values[i] <= 100
解题方法:DFS
以边1-5
为例,这条边最终一定在一个三角形中。在哪个三角形中呢?一共有图中这四种可能。我们分别枚举这4种可能就好了。
具体来说,我们可以写一个函数dfs(i, j)
,代表从i
到j
的凸多边形的最低得分,那么将点k
作为边15
所在三角形的另一个顶点的话,得到的总得分为dfs(i, k)+dfs(k, j) + i*j*k
。
- 时间复杂度$O(n^3)$
- 空间复杂度$O(n^2)$
AC代码
C++
1 |
|
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
1039.多边形三角剖分的最低得分:记忆化搜索(深度优先搜索)
https://blog.letmefly.xyz/2025/10/01/LeetCode 1039.多边形三角剖分的最低得分/