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

张开发
• 2026/4/20 1:53:04 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【算法日记】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(vectorintvalues){intnvalues.size();vectorvectorintdp(n,vectorint(n,0));// 初始化为0边界自动为0// 区间长度从3开始至少三个顶点才能剖分for(intlen3;lenn;len){for(intl0;llen-1n;l){intrllen-1;dp[l][r]INT_MAX;for(intkl1;kr;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, l1, ..., k]对应区间[l, k]右侧子多边形顶点序列[k, k1, ..., r]对应区间[k, r]为什么枚举k是充分的任何合法的三角剖分对于当前区间[l, r]边(l, r)一定是某个三角形的边因为多边形是凸的且l和r不相邻。该三角形的第三个顶点就是某个k因此枚举k即可覆盖所有剖分方式。4. 相关题目LeetCode 1547. 切棍子的最小成本

更多文章