多边形三角剖分的最低得分问题（顶点权重乘积版本）

题目描述
给定一个凸多边形，其顶点按顺时针顺序编号为0到n-1。每个顶点i有一个权重weights[i]。将多边形三角剖分（即用不相交的对角线将多边形分割成n-2个三角形）后，每个三角形的得分是该三角形三个顶点权重的乘积。求所有三角形得分之和的最小值。

例如：weights = [1, 2, 3]
这是一个三角形（无需剖分），得分=123=6

weights = [1, 3, 1, 2, 3]
对应一个五边形，需要三角剖分成3个三角形，求最小总分。

解题过程

1. 问题分析

• 凸多边形的三角剖分问题通常用区间DP解决
• 关键观察：任意三角剖分中，多边形的每条边必然属于某个三角形
• 如果选择顶点i和j之间的对角线（i<j），那么多边形被分成两部分：[i,j]顶点形成的多边形和剩余部分
• 但更通用的思路是：固定多边形的一条边(i,j)，考虑所有可能的第三个顶点k（i<k<j）形成三角形(i,k,j)

2. DP状态定义
定义dp[i][j]表示从顶点i到顶点j（按顺时针顺序）形成的子多边形进行三角剖分后的最小得分和。

• 区间长度L = j-i+1（顶点数）
• 当L < 3时，无法形成三角形，得分为0
• 当L = 3时，就是三角形，得分=weights[i]×weights[i+1]×weights[j]

3. 状态转移方程
对于区间[i,j]（j-i≥2）：

• 选择顶点k（i < k < j）作为三角形的第三个顶点
• 三角形(i,k,j)的得分=weights[i]×weights[k]×weights[j]
• 子问题1：[i,k]区间的多边形
• 子问题2：[k,j]区间的多边形
• 总得分=dp[i][k] + dp[k][j] + weights[i]×weights[k]×weights[j]

状态转移方程：
dp[i][j] = min(dp[i][k] + dp[k][j] + weights[i]×weights[k]×weights[j])，其中k从i+1到j-1

4. 计算顺序

• 按区间长度从小到大计算
• 先计算所有长度为3的区间，然后长度4、5...直到n

5. 示例演示
以weights = [1, 3, 1, 2, 3]为例：

初始化dp表（5×5）：

dp[0][2] = 1×3×1 = 3
dp[1][3] = 3×1×2 = 6  
dp[2][4] = 1×2×3 = 6
dp[0][3]：k=1: dp[0][1]+dp[1][3]+1×3×2=0+6+6=12
          k=2: dp[0][2]+dp[2][3]+1×1×2=3+0+2=5 → min=5
dp[1][4]：k=2: dp[1][2]+dp[2][4]+3×1×3=0+6+9=15
          k=3: dp[1][3]+dp[3][4]+3×2×3=6+0+18=24 → min=15
dp[0][4]：k=1: dp[0][1]+dp[1][4]+1×3×3=0+15+9=24
          k=2: dp[0][2]+dp[2][4]+1×1×3=3+6+3=12
          k=3: dp[0][3]+dp[3][4]+1×2×3=5+0+6=11 → min=11

最终结果：dp[0][4] = 11

6. 算法实现要点

• 时间复杂度：O(n³)，需要三层循环
• 空间复杂度：O(n²)，存储dp表
• 注意边界条件：当j-i<2时，dp[i][j]=0

7. 关键理解点

• 每个三角形由一条边(i,j)和中间顶点k确定
• 三角剖分将多边形分成三个部分：三角形(i,k,j)和两个子多边形
• 通过遍历所有可能的k，找到最优的分割点
• 这种思路可以推广到各种多边形剖分问题