Medium

题目描述

给你一个凸多边形，其顶点按顺时针顺序用整数数组 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

解题思路

这是一个经典的区间动态规划问题。核心思路是将多边形的三角剖分转化为递归子问题。

思路分析：

  • 对于一个多边形，我们需要选择一条边作为基础边，然后在该边的对面选择一个顶点形成三角形
  • 这样就将原问题分解为两个更小的多边形三角剖分问题
  • 使用区间DP，dp[i][j] 表示顶点 i 到顶点 j 形成的多边形的最小三角剖分得分

状态转移：

  • 对于区间 [i, j]，枚举中间点 k（i < k < j）
  • 将多边形分为三部分：三角形 (i, k, j) 和两个子多边形 [i, k]、[k, j]
  • 状态转移方程：dp[i][j] = min(dp[i][k] + dp[k][j] + values[i] * values[k] * values[j])

边界条件：

  • 当 j - i < 2 时，无法形成三角形，得分为 0

时间复杂度 O(n³)，空间复杂度 O(n²)。

代码实现

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = INT_MAX;
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]);
                }
            }
        }
        
        return dp[0][n-1];
    }
};

class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        n = len(values)
        dp = [[0] * n for _ in range(n)]
        
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = float('inf')
                for k in range(i + 1, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j])
        
        return dp[0][n-1]

public class Solution {
    public int MinScoreTriangulation(int[] values) {
        int n = values.Length;
        int[,] dp = new int[n, n];
        
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i, j] = int.MaxValue;
                for (int 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];
    }
}

var minScoreTriangulation = function(values) {
    const n = values.length;
    const dp = Array(n).fill(null).map(() => 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];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n³)
空间复杂度O(n²)