1039. 多边形三角剖分的最低得分【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 区间 DP

1. 📝 题目描述

• leetcode

你有一个凸的 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

2. 🎯 s.1 - 区间 DP

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} values
 * @return {number}
 */
var minScoreTriangulation = function (values) {
  const n = values.length
  const dp = Array.from({ length: n }, () => new Array(n).fill(0))
  for (let len = 3; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1
      dp[i][j] = Infinity
      for (let k = i + 1; k < j; k++) {
        dp[i][j] = Math.min(
          dp[i][j],
          dp[i][k] + dp[k][j] + values[i] * values[k] * values[j],
        )
      }
    }
  }
  return dp[0][n - 1]
}

• 时间复杂度：$O(n^3)$，其中 $n$ 是顶点数
• 空间复杂度：$O(n^2)$，DP 数组

算法思路：

• dp[i][j] 表示将顶点 i 到 j 的多边形进行三角剖分的最低得分
• 枚举中间点 k，将多边形分为三角形 (i, k, j) 和两个子多边形
• 转移方程：dp[i][j] = min(dp[i][k] + dp[k][j] + values[i] * values[k] * values[j])