题目:
      对于一个n个顶点的凸多边形，有很多种方法可以对它进行三角划分，即用n - 3条互不相交的对角线把凸多边形分成n - 2个三角形。对于每个三角形规定一个权函数f(i,j,k)（如三角形的周长或者3个顶点的权和），求让所有三角形权和最大方案。


我的思路（虽然有参考了书上，但还是与作者思路不太一样，我把自己思路都表达出来，还望指出错误）
    1.有状态转移方程为f(i,j) = max(f(i,k) + f(k,j) + w(i,j,k));f(i,j)表示从vi到vj的简单通路(我们默认vj指向vi)，这样才能构成凸多边形，同时表示在这个凸多边形中权和的最大值。
    2.由3边的凸多边形也就是三角形开始递推上去，构建整个动态规划。

下面是代码:

#include <stdio.h>
#define MAXN 1000
int f[MAXN][MAXN];
int w[MAXN][1];
int n;
int ww(int i,int j,int k){
    return w[i][0] + w[j][0] + w[k][0];
}

int main(){
    while(scanf("%d",&n) != EOF){
        
        for(int i =1 ; i <= n; i++){//输入各个顶点权值 
            scanf("%d",&w[i][0]);
        }
        for(int i = 1; i <= n; i++){//无法构成凸边形,说白点就是边为1条 
            f[i][i + 1] = 0;
        } 
        //从通路长度为2的开始递推上去，通路为1即为一条边，通路为2为三角形 
        for(int d = 2; d <= n - 1; d++){//因为最后一个即为n边形，只需要n - 1唱的的通路，加上最后一个顶点指向第一个构成回路，也就是凸多变形，tips:d = 2是三角形
            for(int i = 1; i <= n - d; i++){//枚举起点 
                int j = d + i;//终点 
                f[i][j] = f[i + 1][j] + ww(i,i + 1, j); 
                for(int k = i + 1; k < j; k++){
                    int temp = f[i][k] + f[k][j] + ww(i,j,k);
                    f[i][j] = f[i][j] < temp?f[i][j] : temp;
                }
            }
            
        } 
        printf("%d\n",f[1][n]);
    }
    return 0;
}

我求的是最小，要求最大把比较那边的小于号改掉就行

我记得最优二叉树中，为了使权重达到最大，你把权小的当起始点，权大的放到离起点路径最远的地方应该可以。