区间动态规划例题：多边形三角剖分的最低得分问题

题目描述
给定一个凸多边形，其顶点按顺时针顺序标记为 0, 1, 2, ..., n-1，每个顶点对应一个整数值。多边形的每条边和一条对角线（连接两个非相邻顶点的线段）的权重定义为该边或对角线两端顶点值的乘积。将多边形三角剖分为若干个不相交的三角形后，总得分为所有三角形边的权重之和（多边形的原始边也必须计入）。要求计算三角剖分的最低可能得分。

例如，对于顶点值数组 [1, 3, 1, 4, 2] 对应的五边形，一种三角剖分的得分计算需考虑所有三角形的边权重之和。

解题思路

1. 问题分析

   • 三角剖分将凸多边形划分为 n-2 个三角形，使用 n-3 条对角线。
   • 每条边（包括原始边和对角线）的权重为两端顶点值的乘积。
   • 目标是最小化所有边的权重总和。

2. 区间动态规划定义

   • 定义 dp[i][j] 表示从顶点 i 到顶点 j（连续子多边形）进行三角剖分后的最低得分。
   • 区间长度 len 从 3 开始（三角形是最小单位），逐步扩大到 n。

3. 状态转移

   • 在区间 [i, j] 中，枚举一个中间顶点 k（i < k < j），将多边形划分为三部分：
     1. 子多边形 [i, k]
     2. 子多边形 [k, j]
     3. 三角形 (i, k, j)
   • 得分包括：dp[i][k] + dp[k][j] + weight(i,k) + weight(k,j) + weight(i,j)，但需注意边避免重复计算。
   • 实际上，三角形 (i,k,j) 的三条边中，边 (i,j) 可能是原始边或对角线，需单独处理。更精确的转移方程为：

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

     其中 values[i]*values[j]*values[k] 是三角形 (i,k,j) 中唯一新增的权重（对角线 (i,j) 的权重在其他子问题中未计算过）。

4. 初始化与计算顺序

   • 当 j - i < 2 时，dp[i][j] = 0（无法形成三角形）。
   • 按区间长度从小到大计算。

详细步骤

1. 输入处理

   • 顶点值数组 values，长度 n。

2. DP 表初始化

   • 创建 n x n 的 dp 表，初始值为 0。
   • 对于长度 len = 2 的区间（即三个顶点），直接计算三角形得分。

3. 区间递推

   • 遍历区间长度 len 从 3 到 n（表示顶点数从 4 到 n）：
     • 遍历起点 i，终点 j = i + len - 1（j < n）：
       • 初始化 dp[i][j] 为无穷大。
       • 遍历中间点 k 从 i+1 到 j-1：
         • 得分 = dp[i][k] + dp[k][j] + values[i]*values[k]*values[j]
         • 更新 dp[i][j] 为最小值。

4. 结果输出

   • 最终答案存储在 dp[0][n-1] 中。

示例演示
以 values = [1, 3, 1, 4, 2] 为例：

• 计算 dp[0][4]：
  • 枚举 k=1,2,3，比如 k=2 时：
    • 得分 = dp[0][2] + dp[2][4] + 1*1*2
    • 其中 dp[0][2] 对应三角形 (0,1,2)：权重=1×3 + 3×1 + 1×1=7（实际应直接按公式计算为 1*3*1=3）。
• 最终最小得分通过 DP 表逐层计算得到。

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