多边形三角剖分的最低得分问题（不同描述版本） 题目描述： 给定一个凸多边形，其顶点按顺时针顺序编号为0到n-1，每个顶点有一个权重值。将多边形三角剖分成若干个三角形，每个三角形的得分是三个顶点权重的乘积。求所有三角形得分之和的最小值。 解题过程： 问题分析：我们需要将凸多边形通过不相交的对角线划分成n-2个三角形，使得所有三角形得分之和最小。 定义状态：设dp[ i][ j ]表示从顶点i到顶点j（按顺时针顺序）形成的子多边形进行三角剖分的最小得分。 状态转移：对于子多边形i-j，我们选择一条边ik作为三角形的一条边，那么三角形ikj将子多边形分成三部分：三角形ikj本身、子多边形i-k、子多边形k-j。 状态转移方程：dp[ i][ j] = min(dp[ i][ k] + dp[ k][ j] + weight[ i] weight[ k] weight[ j ])，其中k在区间(i,j)内遍历 初始化：当子多边形只有两个顶点时（即i和j相邻），无法形成三角形，dp[ i][ j ] = 0 计算顺序：按区间长度从小到大计算，从长度为2开始直到长度为n 最终结果：dp[ 0][ n-1 ]表示整个多边形的最小得分 举例说明： 假设有四边形顶点权重为[ 1, 2, 3, 4 ]，计算过程： dp[ 0][ 2 ] = 1×2×3 = 6（三角形0-1-2） dp[ 1][ 3 ] = 2×3×4 = 24（三角形1-2-3） dp[ 0][ 3] = min(dp[ 0][ 1]+dp[ 1][ 3]+1×2×4, dp[ 0][ 2]+dp[ 2][ 3 ]+1×3×4) = min(0+24+8, 6+0+12) = min(32, 18) = 18 这种解法的时间复杂度为O(n³)，空间复杂度为O(n²)。