区间动态规划例题：凸多边形三角剖分的最低得分问题 题目描述 给定一个凸多边形，其顶点按顺时针顺序编号为 \(0, 1, 2, \dots, n-1\)，每个顶点对应一个整数值。将多边形三角剖分（即用不相交的对角线将多边形划分为多个三角形）后，每个三角形的得分定义为三个顶点值的乘积。求所有可能三角剖分中的最低总得分。 解题过程 问题分析 凸多边形的三角剖分可以通过选择不相交的对角线将多边形划分为 \(n-2\) 个三角形。 目标是最小化所有三角形顶点值乘积的总和。 核心思路：定义子问题为连续顶点构成的子多边形的最低得分，通过组合子问题的解得到原问题的最优解。 定义状态 设 \(dp[ i][ j ]\) 表示从顶点 \(i\) 到顶点 \(j\)（连续子多边形）进行三角剖分的最低得分。 注意：子多边形需包含至少三个顶点（即 \(j \geq i+2\)），否则无法形成三角形。 状态转移方程 考虑子多边形 \(i \to j\)，若直接连接 \(i\) 和 \(j\) 作为三角形的一条边，需选择第三个顶点 \(k\)（\(i < k < j\)），将多边形划分为三部分： 三角形 \(i, k, j\)（得分：\(values[ i] \times values[ k] \times values[ j ]\)）。 子多边形 \(i \to k\)（得分：\(dp[ i][ k ]\)）。 子多边形 \(k \to j\)（得分：\(dp[ k][ j ]\)）。 转移方程： \[ dp[ i][ j] = \min_ {k \in [ i+1, j-1]} \left( dp[ i][ k] + dp[ k][ j] + values[ i] \times values[ k] \times values[ j ] \right) \] 解释：通过遍历所有可能的 \(k\)，找到使总得分最小的划分方式。 初始化与边界条件 当子多边形只有两个顶点（即 \(j = i+1\)）时，无法形成三角形，得分初始化为 0。 对于 \(j < i+2\) 的情况，直接设 \(dp[ i][ j ] = 0\)。 计算顺序 按子多边形的长度（即顶点数）从小到大计算： 先计算所有长度为 3 的子多边形（即三角形本身，得分固定为三个顶点值的乘积）。 逐步增加长度，直到覆盖整个多边形 \(0 \to n-1\)。 示例演示 假设顶点值数组为 \([ 1, 3, 1, 2, 2 ]\)，对应五边形： 计算长度为 3 的子多边形： \(dp[ 0][ 2 ] = 1 \times 3 \times 1 = 3\)， \(dp[ 1][ 3 ] = 3 \times 1 \times 2 = 6\)， \(dp[ 2][ 4 ] = 1 \times 2 \times 2 = 4\)。 计算长度为 4 的子多边形（如顶点 0-1-2-3）： 选择 \(k=1\)：得分 = \(dp[ 0][ 1] + dp[ 1][ 3 ] + 1 \times 3 \times 2 = 0 + 6 + 6 = 12\)， 选择 \(k=2\)：得分 = \(dp[ 0][ 2] + dp[ 2][ 3 ] + 1 \times 1 \times 2 = 3 + 0 + 2 = 5\)， 取最小值 \(dp[ 0][ 3 ] = 5\)。 最终计算整个多边形 \(dp[ 0][ 4 ]\)，通过遍历 \(k=1,2,3\) 找到最小得分。 复杂度分析 时间复杂度：\(O(n^3)\)，需要三重循环（长度、起点、分割点）。 空间复杂度：\(O(n^2)\)，用于存储 \(dp\) 表。 通过以上步骤，可系统地求解凸多边形三角剖分的最低得分问题。