凸多边形最优三角剖分 - c++编程基础

动态规划的经典应用----凸多边形最优三角剖分

具体的细节讲解，我就不多说啦。网上很多资料，而且讲的非常详细。下面我贴下我做的，虽然大概思路懂了，但是去实现的时候，还是遇到了很多问题。主要是没有正确的理清思路。写下来记录一下。。

#include  
using namespace std;  
  
#define MAX 1024  
int min[MAX][MAX];//m[i][j]节点i开始的连续j个节点的最小值  
int s[MAX][MAX];//记录需连接的弦  
int dis[MAX][MAX];//一对节点的权值  
  
int weight(int i,int j,int k)//得到任意三个节点的总权值  
{  
    return dis[i][j]+dis[i][k]+dis[j][k];  
}  
  
void printThePath(int i,int j)  
{  
    int k=s[i][j];  
    if(!k)  
        return;  
    cout<




>N; 
    int i,j; 
    for(i=1;i<=N;i++) 
    { 
        for(j=1;j<=N;j++) 
        { 
            cin>>dis[i][j]; 
            if(j<3) 
                min[i][j]=0; 
            else 
                min[i][j]=MAX; 
        } 
    }*/  
      
    int temp;  
    int k;  
    for(j=3;j<=N;j++)  
    {  
        for(i=1;i<=N-j+2;i++)  
        {  
            for(k=i+1;k