算法导论上一道dp，挺有趣的。于是就研究了一阵。
dp(i, j)代表从左边第一个点到第i个点与从从左边最后一个点（即为第一个点）到j点的最优距离和。于是找到了子状态。
决策过程 dp[i][j] = min{dp[i-1][j] + Dis(i, i - 1), dp[i - 1][k] + Dis(k, i)} 即可。代表意思是选择最优的路径加入到回路中的去途或者归途中。
一下是代码。
/****************************************/
/***** Desgard_Duan *****/
/****************************************/
//#pragma comment(linker, "/STACK:102400000,102400000")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <functional>
#include <cmath>
#include <numeric>
#include <limits.h> using namespace std; inline void get_val(int &a) {
int value = , s = ;
char c;
while ((c = getchar()) == ' ' || c == '\n');
if (c == '-') s = -s; else value = c - ;
while ((c = getchar()) >= '' && c <= '')
value = value * + c - ;
a = s * value;
} vector<pair<double, double> > P;
int n;
double x, y, dis[][], dp[][]; double caldis (double x1, double y1, double x2, double y2) {
return sqrt ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
} int main () {
while (~scanf ("%d", &n)) {
P.clear();
memset (dis, , sizeof (dis));
memset (dp , , sizeof (dp));
for (int i = ; i < n; ++ i) {
scanf ("%lf %lf", &x, &y);
P.push_back (make_pair(x, y));
}
for (int i = ; i < P.size(); ++ i) {
for (int j = ; j < P.size(); ++ j) {
dis[i + ][j + ] = dis[j + ][i + ]
= caldis (P[i].first, P[i].second, P[j].first, P[j].second);
}
} dp[][] = dis[][];
//cout << dp[1][2] << endl;
for (int j = ; j <= n; ++ j) {
for (int i = ; i <= j - ; ++ i) {
dp[i][j] = dp[i][j - ] + dis[j - ][j];
} dp[j - ][j] = UINT_MAX; for (int k = ; k <= j - ; ++ k) {
dp[j - ][j] = min (dp[j - ][j], dp[k][j - ] + dis[k][j]);
}
}
dp[n][n] = dp[n - ][n] + dis[n - ][n];
printf ("%.2lf\n", dp[n][n]);
}
return ;
}