7-3 凸多边形最优三角剖分 (10 分)(思路+详解+分析题意+动态规划)Come Baby_多边形最优剖分

四：上码：

====================================================================

/**

分析：

1.凸多边形的三角剖分是将凸多边形分割成互不相交的三角

形的弦的集合。

2.最优三角剖分中诸三角形上权值和：指的是将多边形划分成多个三角形

其所有的三角形的周长和最小

3.和矩阵连相乘的思路比较：凸三角形的剖分是通过一个三角形将多边形划分成不同的两部分

和一个三角形。

联想矩阵链的递推方程：将其划分成两个不同的子链+这两个自链所构成的矩阵乘法次数

相同点：两种思路一致，

不同点：矩阵连计算次数是 pi-1 * pK* pj

多变形是 三边之和

4.关于递推方程：t[i][j] = t[i][k] + t[k+1][j] + w(i-1,k,j);

这里需要说明的是t[i][j]即表示的是多边形的剖分最小权值和（所有三角形的）

比如t[1][6] = t[1][1] + t[2][6] + w(0,1,6),

通过点0，1，6将多边形剖分成三部分

其中t[1][1] = 0(三角剖分中 只有一条边的是不可以 被剖分成 多边形的 故其权值和为0)

t[2][6] 表示的是剩下的多变形，然后再求取它的最小值

通过这样的分析：我们可以得知 t[2][6],也就相当于矩阵连相乘问题中的

子链，那么我就还是可以通过建网格来存储每个多边形的最小权值和

来进行求解

5.本题题解：

通过上述分析我们可以得出：

求取凸多边形最优三角剖分 = t[1][n];

*/

#include<bits/stdc++.h>

using namespace std;

int array1[200][200];

//剖分三角形的周长

int C_triangle(int i,int k,int j){

return array1[i][k] + array1[k][j] + array1[i][j];

}

int main(){

int N;

cin >> N;

int m[200][200];

//比如有7个顶点（v0,v1…v6）,我们数组中存的是边长和弦长

for(int i = 0; i < N; i++){

for(int j = i; j < N; j++){

cin >> array1[i][j];

}

}

// for(int i = 1; i <= N; i++){

// for(int j = 1; j <= N; j++){

// cout << array[i][j] << ’ ';

// }

// cout << endl;

// }

for(int i = 0; i <= N; i++){

m[i][i] = 0;

}

//开始划分网格和更新

for(int i = N - 1; i >= 1; i–){

for(int j = i+1; j <= N - 1; j++){//这里j从i+1开始，因为从i开始每次m[i][i] = 0; 这里j <= N 表示的是这一行到最后比如m[i][N]

//初始化二维数组

m[i][j] = m[i][i] + m[i+1][j] + C_triangle(i-1,i,j);

for(int k = i+1; k < j; k++){

int temp = m[i][k] + m[k+1][j] + C_triangle(i-1,k,j);

if(temp < m[i][j]){

m[i][j] = temp;

}

}

}

}

// for(int i = 1; i < N; i++){

// for(int j = 1; j < N; j++){

// cout << m[i][j] << ’ ';

// }

// cout << endl;

// }

// cout << C_triangle(4,5,6);

cout << m[1][N-1];

}

加油陌生人！我们共勉！如有疑问请留言！

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录大纲截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且后续会持续更新

如果你觉得这些内容对你有帮助，可以添加V获取：vip1024b （备注Java）

最后

为什么我不完全主张自学？
①平台上的大牛基本上都有很多年的工作经验了，你有没有想过之前行业的门槛是什么样的，现在行业门槛是什么样的？以前企业对于程序员能力要求没有这么高，甚至十多年前你只要会写个“Hello World”，你都可以入门这个行业，所以以前要入门是完全可以入门的。
②现在也有一些优秀的年轻大牛，他们或许也是自学成才，但是他们一定是具备优秀的学习能力，优秀的自我管理能力（时间管理，静心坚持等方面）以及善于发现问题并总结问题。
如果说你认为你的目标十分明确，能做到第②点所说的几个点，以目前的市场来看，你才真正的适合去自学。

除此之外，对于绝大部分人来说，报班一定是最好的一种快速成长的方式。但是有个问题，现在市场上的培训机构质量参差不齐，如果你没有找准一个好的培训班，完全是浪费精力，时间以及金钱，这个需要自己去甄别选择。

我个人建议线上比线下的性价比更高，线下培训价格基本上没2W是下不来的，线上教育现在比较成熟了，此次疫情期间，学生基本上都感受过线上的学习模式。相比线下而言，线上的优势以我的了解主要是以下几个方面：
①价格：线上的价格基本上是线下的一半；
②老师：相对而言线上教育的师资力量比线下更强大也更加丰富，资源更好协调；
③时间：学习时间相对而言更自由，不用裸辞学习，适合边学边工作，降低生活压力；
④课程：从课程内容来说，确实要比线下讲的更加深入。

应该学哪些技术才能达到企业的要求？（下图总结）

①价格：线上的价格基本上是线下的一半；
②老师：相对而言线上教育的师资力量比线下更强大也更加丰富，资源更好协调；
③时间：学习时间相对而言更自由，不用裸辞学习，适合边学边工作，降低生活压力；
④课程：从课程内容来说，确实要比线下讲的更加深入。

应该学哪些技术才能达到企业的要求？（下图总结）

[外链图片转存中…(img-xgAlfJpP-1711905358455)]

[外链图片转存中…(img-O9xiDNZk-1711905358455)]