凸多边形的最优三角剖分问题

问题描述
给定一个凸n边形，顶点按顺时针顺序编号为0到n-1。每个顶点有一个权重值weights[i]。将多边形三角剖分（用不相交的对角线将多边形划分为n-2个三角形），定义三角剖分的分数为所有三角形的权重之和，其中每个三角形的权重等于其三个顶点权重的乘积。请计算三角剖分的最低可能分数。

例如，对于顶点权重为[1, 2, 3, 4]的凸四边形：

• 对角线0-2：三角形(0,1,2)分数=1×2×3=6，三角形(0,2,3)分数=1×3×4=12，总分=18
• 对角线1-3：三角形(0,1,3)分数=1×2×4=8，三角形(1,2,3)分数=2×3×4=24，总分=32
  因此最低分数是18。

解题过程

第一步：理解问题结构
凸多边形三角剖分问题具有典型的区间结构：

• 多边形顶点按顺序排列，形成一个环
• 任何对角线(i,j)将多边形分成两个子多边形
• 子问题也是凸多边形的三角剖分问题

第二步：定义状态
定义dp[i][j]表示从顶点i到顶点j（按顺时针顺序）形成的凸多边形的最低三角剖分分数，其中i < j。

由于是环状结构，我们需要考虑跨越起点的情况。处理方法是：将环复制一份，变成2n长度的数组，然后求解长度为n的区间。

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

• 如果j-i = 2，即三角形，dp[i][j] = weights[i] × weights[i+1] × weights[j]
• 如果j-i > 2，我们需要选择分割点k（i < k < j）
  dp[i][j] = min(dp[i][k] + dp[k][j] + weights[i] × weights[k] × weights[j])

解释：选择对角线(i,k,j)将多边形分成三部分：

1. 子多边形[i,k]的三角剖分分数：dp[i][k]
2. 子多边形[k,j]的三角剖分分数：dp[k][j]
3. 当前三角形(i,k,j)的分数：weights[i] × weights[k] × weights[j]

第四步：边界条件

• 当j-i < 2时，无法形成三角形，dp[i][j] = 0
• 当j-i = 2时，dp[i][j] = weights[i] × weights[i+1] × weights[j]

第五步：计算顺序
由于需要小区间的结果来计算大区间，我们按区间长度从小到大计算：

1. 初始化长度为2的区间（实际是三角形）
2. 逐步计算长度更大的区间
3. 最终结果是dp[0][n-1]

第六步：算法实现

def min_triangulation_score(weights):
    n = len(weights)
    dp = [[0] * n for _ in range(n)]
    
    # 按区间长度遍历
    for length in range(2, n):  # length = j-i
        for i in range(n - length):
            j = i + length
            dp[i][j] = float('inf')
            
            # 尝试所有可能的分割点
            for k in range(i + 1, j):
                cost = (dp[i][k] + dp[k][j] + 
                       weights[i] * weights[k] * weights[j])
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

第七步：示例验证
以权重[1, 2, 3, 4]为例：

• dp[0][2] = 1×2×3 = 6
• dp[1][3] = 2×3×4 = 24
• dp[0][3] = min(
  dp[0][1] + dp[1][3] + 1×2×4 = 0 + 24 + 8 = 32,
  dp[0][2] + dp[2][3] + 1×3×4 = 6 + 0 + 12 = 18
  ) = 18

结果与手工计算一致。

第八步：复杂度分析

• 时间复杂度：O(n³)，三重循环
• 空间复杂度：O(n²)，dp数组的大小

这个算法能有效解决凸多边形的最优三角剖分问题，是区间动态规划的经典应用。