LeetCode：1039.多边形三角剖分的最低得分

题目：1039.多边形三角剖分的最低得分 ↗

核心逻辑：从一条边开始“切分”#

假设有一个凸 $n$ 边形，顶点数值存在数组 $A$ 中。我们的目标是将它剖分成 $n-2$ 个三角形，使得所有三角形顶点的乘积之和最小。

可以想象手中拿着一个凸多边形，每次切去一个角（一个三角形），直到最后只剩一个三角形。因此与其纠结「第一次切去哪个三角形」，不如考虑「最后保留哪个三角形」。

对于任何一个由顶点 $i$ 到顶点 $j$ 构成的多边形（记为区间 $[i, j]$），我们可以固定底边（连接顶点 $i$ 和 $j$ 的边）。在最终的剖分方案中，这条底边一定属于某一个三角形。

假设这个三角形的第三个顶点是 $k$（其中 $k$ 在 $i$ 和 $j$ 之间），那么这个三角形 $(i, k, j)$ 就把原来的多边形切成了三部分：

1. 左边： 由顶点 $i$ 到 $k$ 构成的多边形。
2. 中间： 三角形 $(i, k, j)$ 本身。
3. 右边： 由顶点 $k$ 到 $j$ 构成的多边形。

定义状态与转移方程#

• 状态定义：$dp[i][j]$ 表示从顶点 $i$ 到顶点 $j$ 连成的子多边形进行三角剖分后的最低得分。
• 转移方程： 我们需要枚举 $i$ 和 $j$ 之间所有的可能顶点 $k$： $dp[i][j] = \min_{i < k < j} \{ dp[i][k] + dp[k][j] + A[i] \times A[k] \times A[j] \}$
• 边界条件：
  • 如果 $i$ 和 $j$ 之间没有顶点（即 $j - i < 2$），无法形成三角形，$dp[i][j] = 0$。
  • 当 $j - i = 2$ 时，$dp[i][j]$ 就是唯一的那个三角形 $A[i] \times A[i+1] \times A[j]$。

遍历顺序#

观察方程，$dp[i][j]$ 依赖于 $dp[i][k]$ 和 $dp[k][j]$：

• $dp[i][k]$：在 $dp[i][j]$ 的左侧（同一行）。
• $dp[k][j]$：在 $dp[i][j]$ 的下方（不同行，$k > i$）。

因此，遍历顺序与516.最长回文子序列一致：$i$ 从大到小（从下往上），$j$ 从小到大（从左往右）。

代码实现#

public int minScoreTriangulation(int[] values) {
    int n = values.length;
    int[][] dp = new int[n][n];

    // i 从下往上遍历
    for (int i = n - 3; i >= 0; i--) {
        // j 从左往右遍历，且 j 与 i 之间至少要隔一个点
        for (int j = i + 2; j < n; j++) {
            // 初始化为一个较大值
            int minRes = Integer.MAX_VALUE;
            // 枚举中间顶点 k
            for (int k = i + 1; k < j; k++) {
                int score = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
                minRes = Math.min(minRes, score);
            }
            dp[i][j] = minRes;
        }
    }
    return dp[0][n - 1];
}