【算法日记】Day 11 动态规划专题——区间DP之基于范围中划分点的讨论

Abstract：#动态规划#区间DP#多边形剖分

1. 题目

• 题目：LeetCode 1039. 多边形三角剖分的最低得分
• 核心思路：定义dp[i][j]表示从顶点i到顶点j构成的多边形（凸多边形，顶点按顺序排列）通过三角剖分能得到的最小得分。转移时，在(i, j)之间枚举一个中间顶点k，将多边形分为三部分：三角形(i, k, j)、子多边形(i, …, k)和(k, …, j)。得分为dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]。取所有k的最小值。
• 复杂度：时间复杂度O ( n 3 ) O(n³)O(n3)，空间复杂度O ( n 2 ) O(n²)O(n2)。

2. 代码

classSolution{public:intminScoreTriangulation(vector<int>&values){intn=values.size();vector<vector<int>>dp(n,vector<int>(n,0));// 初始化为0，边界自动为0// 区间长度从3开始（至少三个顶点才能剖分）for(intlen=3;len<=n;++len){for(intl=0;l+len-1<n;++l){intr=l+len-1;dp[l][r]=INT_MAX;for(intk=l+1;k<r;++k){dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+values[l]*values[r]*values[k]);}}}returndp[0][n-1];}};

3. 心得

• 边界情况：当r - l < 2（即少于3个顶点）时，多边形无法剖分，得分为0。

• 划分点的角色：顶点k必须位于l和r之间（l < k < r），它与l、r构成一个三角形(l, k, r)。这个三角形将原多边形分成三部分：

  • 三角形(l, k, r)的得分：values[l] * values[r] * values[k]
  • 左侧子多边形：顶点序列[l, l+1, ..., k]，对应区间[l, k]
  • 右侧子多边形：顶点序列[k, k+1, ..., r]，对应区间[k, r]

• 为什么枚举k是充分的：任何合法的三角剖分，对于当前区间[l, r]，边(l, r)一定是某个三角形的边（因为多边形是凸的，且l和r不相邻）。该三角形的第三个顶点就是某个k，因此枚举k即可覆盖所有剖分方式。

4. 相关题目

• LeetCode 1547. 切棍子的最小成本