学步园

N个点来回路径最小：

2013年Hulu面试中出现过。

二维平面上有n个点，已按照x坐标从左到右排序（所有点的x坐标均不同），存放在数组points中。

需要从最左边的点出发，先向右扫描访问一些点，到达最右边的点，然后再向左扫描，访问第一次没有访问的点，最后回到最左边的点。扫描过程中经过的总的欧式距离要最小。返回这个最小的欧式距离。

样例：

points (x,y) : [(0, 0), (30, 40), (31, 0)]

最优路径为 (0, 0) -> (31, 0) -> (30,40) -> (0, 0)，总的距离为121.012，因此函数应返回121.012。

这个题跟之前两条路径求最大收获的题一样的，也是从起始点同时发两条路径出去，然后计算这个距离。

记 cost [i] [j] 表示 从起始点出发 第一条路径停在 i 点，第二条路径停在 j 点时候的距离总和。

注意我们总是讨论 i 在 j 点后边的情况，即 i 点离起点远。 当  i < j 的时候  cost [i][j] = cost [j] [i] 

所以我们这么看，当我们计算 cost [ i ] [ j ]  的时候，如果 i , j 中间有其他点， 那么这些点肯定是属于 i 这条路径的，因为本来 i 跟 j 就分别表示两条路径到达的最远点。

所以 (i ,j ) 这个状态肯定来自与 (i-1 ,j ) ，所以  cost = cost[ i-1] [ j ] + dist ( i-1, i )

如果i 和j 挨着的，那么 i 可以来自于前面的每个点 ，所以要枚举这个K ，然后取最小值。

注意我只计算 i > j 的情况，另外一半没有算，所以枚举 k <j ， 要用 cost [j ][ k] 而不是 cost [k ][j ]， 如果你两半都计算，并且在  i< j 的时候直接 cost[i][j] = cost [ j ] [ i ]，那么就不用这样。

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
struct Point {int x,y;};

double dist(vector<Point>& points,int i,int j)
{
	double gapx=abs(points[j].x-points[i].x);
	double gapy=abs(points[j].y-points[i].y);
	double sum=gapx*gapx+gapy*gapy;
	return sqrt(sum);
}
double minDist(vector<Point> &points) {
	int n=points.size();
	vector<vector<double> > cost(n,vector<double>(n,1000000.0));
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=i;j++)
		{
			if(i==0||j==0)
			{
				if (i==0&&j==0)
				{
					cost[i][j]=0;
					continue;
				}
				if(i==0)
					cost[i][j]=cost[0][j-1]+dist(points,j-1,j);
				else
					cost[i][j]=cost[i-1][0]+dist(points,i,i-1);
				continue;
			}
			if(i==j&&i!=n-1)
			{
				cost[i][j]=1000000.0;
				continue;
			}
			double minCost=1000000.0;
			if(i-j>1)
			{
				minCost=min(minCost,cost[i-1][j]+dist(points,i-1,i));
			}
			else
			{
				for(int k=j;k>=0;k--)
				{
					minCost=min(minCost,cost[j][k]+dist(points,k,i));
				}
			}
			
			cost[i][j]=minCost;
		}
	}
	return cost[n-1][n-1];
}


int main()
{
	int n;
	while(cin>>n)
	{
		vector<Point> points(n);
		for(int i=0;i<n;i++)
		{
			cin>>points[i].x>>points[i].y;
		}
		double dis= minDist(points);
		cout << dis <<endl;
	}
}