区间动态规划例题：多边形三角剖分的最低得分问题（顶点权重乘积版本）

我将为您详细讲解多边形三角剖分问题的一个变种——顶点权重乘积版本。这个问题是区间动态规划的经典应用，通过将多边形分解为三角形来优化某种目标函数。

问题描述

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

例如，对于一个四边形(4个顶点)，权重为[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。

问题分析

1. 问题特征：凸多边形、三角剖分、最小化顶点权重乘积之和
2. 关键观察：任何三角剖分都会将多边形分解为若干个三角形，每个三角形由三个相邻（在多边形中）的顶点组成
3. 区间特性：考虑从顶点i到顶点j的连续子多边形，可以用区间动态规划求解

动态规划解法

状态定义

定义dp[i][j]表示从顶点i到顶点j的连续子多边形（包含顶点i和j）进行三角剖分后的最小得分总和。

这里i和j表示多边形的顶点索引，且我们只考虑i ≤ j的情况。由于多边形是环形的，我们需要特殊处理跨越边界的情况。

状态转移方程

对于区间[i,j]：

• 如果j - i < 2，即少于3个顶点，无法形成三角形，dp[i][j] = 0
• 否则，我们选择顶点k (i < k < j)，将多边形分割为：
  • 三角形(i,k,j)
  • 子多边形[i,k]
  • 子多边形[k,j]

状态转移方程为：
dp[i][j] = min(dp[i][k] + dp[k][j] + w[i]×w[k]×w[j])，其中i < k < j

边界条件

• 当j - i < 2时，dp[i][j] = 0（无法形成三角形）
• 当j - i = 2时，dp[i][j] = w[i]×w[i+1]×w[j]（只有一个三角形）

计算顺序

由于区间动态规划的特性，我们需要按照区间长度从小到大计算：

1. 先计算所有长度为2的区间（实际是3个顶点）
2. 然后计算长度为3的区间（4个顶点）
3. 依此类推，直到计算整个多边形

详细解题步骤

让我们通过一个具体例子来理解：五边形，顶点权重为[1, 2, 3, 4, 5]

步骤1：初始化
创建dp表格，大小为5×5，初始化为0

步骤2：计算基础情况（3个顶点）

• dp[0][2] = w[0]×w[1]×w[2] = 1×2×3 = 6
• dp[1][3] = w[1]×w[2]×w[3] = 2×3×4 = 24
• dp[2][4] = w[2]×w[3]×w[4] = 3×4×5 = 60
• dp[3][0] = 由于环形特性，需要特殊处理
• dp[4][1] = 由于环形特性，需要特殊处理

步骤3：处理环形特性
对于环形多边形，我们需要考虑所有可能的起点。一个常用技巧是将原数组复制一份，然后在新数组上计算长度为n的区间。

新数组：w' = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
然后计算所有长度为n的区间的最小值。

步骤4：计算4个顶点的情况（区间长度=3）
以区间[0,3]为例：

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

步骤5：计算5个顶点的情况（区间长度=4）
以区间[0,4]为例：

• k=1: dp[0][1] + dp[1][4] + w[0]×w[1]×w[4] = 0 + ? + 1×2×5
• k=2: dp[0][2] + dp[2][4] + w[0]×w[2]×w[4] = 6 + 60 + 1×3×5 = 81
• k=3: dp[0][3] + dp[3][4] + w[0]×w[3]×w[4] = 18 + 0 + 1×4×5 = 38

需要先计算dp[1][4]：

• k=2: dp[1][2] + dp[2][4] + w[1]×w[2]×w[4] = 0 + 60 + 2×3×5 = 90
• k=3: dp[1][3] + dp[3][4] + w[1]×w[3]×w[4] = 24 + 0 + 2×4×5 = 64
  dp[1][4] = min(90, 64) = 64

回到dp[0][4]：

• k=1: 0 + 64 + 10 = 74
• k=2: 6 + 60 + 15 = 81
• k=3: 18 + 0 + 20 = 38
  dp[0][4] = min(74, 81, 38) = 38

步骤6：最终结果
由于是环形，我们需要考虑所有可能的起点，取最小值：
min(dp[0][4], dp[1][0], dp[2][1], dp[3][2], dp[4][3]) = 38

算法实现

def min_score_triangulation(weights):
    n = len(weights)
    # 扩展数组处理环形
    extended_weights = weights + weights
    
    # dp[i][j] 表示从i到j的子多边形的最小得分
    dp = [[0] * (2*n) for _ in range(2*n)]
    
    # 按区间长度从小到大计算
    for length in range(2, n):  # length表示顶点数-1
        for i in range(2*n - length):
            j = i + length
            dp[i][j] = float('inf')
            for k in range(i+1, j):
                dp[i][j] = min(dp[i][j], 
                              dp[i][k] + dp[k][j] + 
                              extended_weights[i] * extended_weights[k] * extended_weights[j])
    
    # 在所有长度为n的区间中找最小值
    result = float('inf')
    for i in range(n):
        result = min(result, dp[i][i+n-1])
    
    return result

# 测试示例
weights = [1, 2, 3, 4, 5]
print(min_score_triangulation(weights))  # 输出: 38

复杂度分析

• 时间复杂度：O(n³)，三重循环
• 空间复杂度：O(n²)，用于存储dp表

关键点总结

1. 环形处理：通过数组扩展技巧将环形问题转化为线性问题
2. 区间划分：通过选择中间顶点k将多边形划分为更小的子问题
3. 最优子结构：整体最优解包含子问题的最优解
4. 计算顺序：按区间长度从小到大计算，确保子问题先被解决

这个问题的核心思想是将复杂的多边形分解问题转化为可管理的子问题，通过动态规划逐步构建最优解。