学步园

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

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

#include<iostream>
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<<i<<" "<<i+j-1<<" "<<s[i][j]<<endl;
	printThePath(i,k-i+1);
	printThePath(k,i+j-k);
}
void main()
{
	//可以自己输入
	int N=6;
	dis[1][1]=0;
	dis[1][2]=2;
	dis[1][3]=2;
	dis[1][4]=3;
	dis[1][5]=1;
	dis[1][6]=4;

	dis[2][1]=2;
	dis[2][2]=0;
	dis[2][3]=1;
	dis[2][4]=5;
	dis[2][5]=2;
	dis[2][6]=3;

	dis[3][1]=2;
	dis[3][2]=1;
	dis[3][3]=0;
	dis[3][4]=2;
	dis[3][5]=1;
	dis[3][6]=4;

	dis[4][1]=3;
	dis[4][2]=5;
	dis[4][3]=2;
	dis[4][4]=0;
	dis[4][5]=6;
	dis[4][6]=2;

	dis[5][1]=1;
	dis[5][2]=2;
	dis[5][3]=1;
	dis[5][4]=6;
	dis[5][5]=0;
	dis[5][6]=1;

	dis[6][1]=4;
	dis[6][2]=3;
	dis[6][3]=4;
	dis[6][4]=2;
	dis[6][5]=1;
	dis[6][6]=0;
	int i,j;
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=N;j++)
		{
			
			if(j<3)
				min[i][j]=0;
			else
				min[i][j]=MAX;
		}
	}
	/*
	cout<<"输入多边形点的个数:";
	cin>>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<i+j-1;k++)
			{
				
				temp=weight(i,k,i+j-1)+min[i][k-i+1]+min[k][i+j-k];//动态规划的核心
				if(temp<min[i][j])
				{
					min[i][j]=temp;
					s[i][j]=k;
				}
			}
		}

		for(i=1;i<=N-j+2;i++)
		{
			cout<<"min["<<i<<"]["<<j<<"]="<<min[i][j]<<" ";
		}
		cout<<endl;
	}
	
	cout<<min[1][N]<<endl;
	
	cout<<"三角形剖片为:"<<endl;
	printThePath(1,N);
}