LeetCode 题解工作台
多边形三角剖分的最低得分
你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是按 顺时针顺序 第 i 个顶点的值。 假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的 乘积 ，三角剖分的分数是进行三角剖分后所有 n - 2 个三角…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $\text{dfs}(i, j)$，表示将多边形的顶点 到 进行三角剖分后的最低分数。那么答案就是 $\text{dfs}(0, n - 1)$。 函数 $\text{dfs}(i, j)$ 的计算过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
你有一个凸的 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.length3 <= n <= 501 <= values[i] <= 100
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示将多边形的顶点 到 进行三角剖分后的最低分数。那么答案就是 。
函数 的计算过程如下：
如果 ，说明多边形只有两个顶点，无法进行三角剖分，返回 ；
否则，我们枚举 和 之间的一个顶点 ，即 ，将多边形的顶点 到 进行三角剖分，可以分为两个子问题：将多边形的顶点 到 进行三角剖分，以及将多边形的顶点 到 进行三角剖分。这两个子问题的最低分数分别为 和 ，而顶点 , 和 构成的三角形的分数为 。那么，此次三角剖分的最低分数为 ，我们取所有可能的最小值，即为 的值。
为了避免重复计算，我们可以使用记忆化搜索，即使用哈希表或者数组来存储已经计算过的函数值。
最后，我们返回 即可。
时间复杂度 ，空间复杂度 。其中 为多边形的顶点数。
class Solution:
def minScoreTriangulation(self, values: List[int]) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i + 1 == j:
return 0
return min(
dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j]
for k in range(i + 1, j)
)
return dfs(0, len(values) - 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^3) because each of the O(n^2) subproblems checks O(n) possible k splits. Space complexity is O(n^2) for storing the DP table. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on state transition dynamic programming for polygon subproblems.
- question_mark
Check whether the DP correctly handles all subpolygon combinations.
- question_mark
Expect reasoning about triangle vertex products and minimal sums.
常见陷阱
外企场景- error
Forgetting that a triangle must use original polygon vertices only.
- error
Misindexing DP ranges or skipping subpolygons of length 3.
- error
Not considering all possible k splits between i and j, missing minimal scores.
进阶变体
外企场景- arrow_right_alt
Compute maximal score instead of minimal by adjusting DP comparisons.
- arrow_right_alt
Allow polygons with negative vertex values affecting triangle weight.
- arrow_right_alt
Optimize for memory by using a rolling DP table if needed.