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

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

解题过程

1. 问题分析

   • 凸多边形的三角剖分问题可以通过区间动态规划求解，因为剖分过程可以分解为子多边形的剖分。
   • 定义状态dp[i][j]表示从顶点i到顶点j（连续区间）形成的子多边形的最小总分。
   • 最终目标是求dp[0][n-1]。

2. 状态转移方程

   • 对于区间[i, j]，若j - i < 2，无法形成三角形，得分为0。
   • 否则，枚举中间顶点k（i < k < j），将多边形分割为三部分：
     • 三角形(i, k, j)
     • 子多边形[i, k]
     • 子多边形[k, j]
   • 转移方程：

     dp[i][j] = min(dp[i][k] + dp[k][j] + weight[i] * weight[k] * weight[j])
     

     其中k遍历i+1到j-1。

3. 初始化与计算顺序

   • 初始化：当区间长度小于3时（即j-i<2），dp[i][j] = 0。
   • 计算顺序：按区间长度从小到大计算，长度从3开始（即三角形）到n。

4. 示例演示
   假设顶点权重为[1, 2, 3, 4]，n=4：

   • 区间[0,2]：三角形(0,1,2)，得分=123=6。
   • 区间[1,3]：三角形(1,2,3)，得分=234=24。
   • 区间[0,3]：有两种剖分：
     • 以k=1：三角形(0,1,3) + 子区间[1,3] → 得分=124 + 24 = 32。
     • 以k=2：三角形(0,2,3) + 子区间[0,2] → 得分=134 + 6 = 18。
     • 最小值dp[0][3] = 18。

5. 算法实现要点

   • 注意顶点序列是环形的，但问题本身是线性区间DP，因为凸多边形顶点已按顺序排列。
   • 时间复杂度O(n³)，空间复杂度O(n²)。

通过以上步骤，可系统地求解凸多边形三角剖分的最小得分问题。