多边形三角剖分的最低得分问题（顶点权重乘积版本） 题目描述 给定一个凸N边形，顶点按顺时针顺序标记为0到N-1。每个顶点i有一个权重weights[ i ]。将多边形三角剖分为N-2个三角形，每个三角形的得分为其三个顶点权重的乘积。求所有三角形得分之和的最小值。 解题过程 第一步：理解问题本质 三角剖分：用不相交的对角线将多边形分割成三角形 目标：找到使所有三角形得分之和最小的剖分方式 关键观察：每个三角形由连续的三个顶点构成，剖分过程可以递归进行 第二步：定义状态 定义dp[ i][ j ]表示从顶点i到顶点j（包含i和j）形成的子多边形进行三角剖分的最小得分和。 区间长度：j-i+1（至少为3，即三角形） 基础情况：当j-i < 2时，无法形成三角形，得分为0 第三步：状态转移方程 对于区间[ i,j]，选择中间顶点k(i < k < j)将多边形分成三部分： 三角形(i,k,j) 子多边形[ i,k ]的三角剖分 子多边形[ k,j ]的三角剖分 状态转移方程： dp[ i][ j] = min(dp[ i][ k] + dp[ k][ j] + weights[ i] * weights[ k] * weights[ j ])，其中k从i+1到j-1 第四步：计算顺序 按区间长度从小到大计算： 先计算长度为3的区间（三角形本身） 然后计算长度为4、5...直到N的区间 第五步：具体示例 假设顶点权重为[ 1, 2, 3, 4 ]，对应四边形顶点0-1-2-3： 计算过程： 区间[ 0,2 ]：三角形(0,1,2)，得分1×2×3=6 区间[ 1,3 ]：三角形(1,2,3)，得分2×3×4=24 区间[ 0,3 ]：有两种剖分方式： 选择k=1：得分=dp[ 0,1]+dp[ 1,3 ]+1×2×4=0+24+8=32 选择k=2：得分=dp[ 0,2]+dp[ 2,3 ]+1×3×4=6+0+12=18 最小得分：min(32,18)=18 第六步：算法实现要点 初始化dp数组为0 外层循环遍历区间长度len从3到N 内层循环遍历起始点i从0到N-len 计算j=i+len-1 内层循环遍历分割点k从i+1到j-1 第七步：复杂度分析 时间复杂度：O(N³)，三重循环 空间复杂度：O(N²)，存储dp表 这种方法的本质是通过最优子结构性质，将大问题分解为小问题，逐步构建出全局最优解。