由于x坐标不同，设为x0, x1, x2, ..., xn，则可以用0, 1, 2, ..., n来表示这些点。
构造一个distance表d[i, j] = distance(i, j)  (i < j)

设有正向路径a0 = 0 < a1 < a2 ... < ai = p 从0点顺序到达p点，
有回程路径bj = q > b(j-1) ... > b0 = 0 从q点顺序到回到0点，两路径覆盖了0..p中的所有的点。
且p > q. 令w(p, q)为所有这些路径中路程最小的路径的路程。

则由定义，
w(p, q) = min{sum(k = 0 to i-1){d[a(k), a(k+1)]} + sum(k = 0 to j-1){d[b(k), b(k+1)]}}
 = min{ sum(k = 0 to i-2){d[a(k), a(k+1)]} + sum(k = 0 to j-2){d[b(k), b(k+1)]}
        + d[a(i-1), p] + d[b(j-1), q] }
由于0..p均必须包含在路径中，所以p-1必定包含在某路径中，
由于单调性，当q != p-1时，必有a(i-1) = p-1，否则，有q = p-1.

1.当q < p-1时，
w(p, q) = min{ sum(k = 0 to i-2){d[a(k), a(k+1)]} + sum(k = 0 to j-2){d[b(k), b(k+1)]}
               + d[p-1, p] + d[b(j-1), q] }
 = d[p-1, p] + min(b(j-1) = 0 to q-1){w(p-1, b(j-1)) + d[b(j-1), q]}

注：以上将两个sum换成w基于以下（至少我认为是）事实：min{a + b} = min{ min{a} + b }，其中a, b

为某集合，a+b表示其中元素任意相加后的集合。（这条如果错了，以上一下全是胡扯 :P ）

2.当q = p-1时，
w(p, q) = min{ sum(k = 0 to i-2){d[a(k), a(k+1)]} + sum(k = 0 to j-2){d[b(k), b(k+1)]}
               + d[a(i-1), p] + d[b(j-1), p-1] }
 = min{ sum(k = 0 to i-2){d[a(k), a(k+1)]} + sum(k = 0 to j-1){d[b(k), b(k+1)]
        + d[a(i-1), p] }
观察前面的两个sum，由于b(j) = p-1 有 a(i-1) != p, 又 a(i-1) < p, 故a(i-1) < p-1.
交换路径a和b, 这个sum就变成了w(p-1, a(i-1)).
于是，有
w(p, q) = min(a(i-1) = 0 to p-2){w(p-1, a(i-1)) + d[a(i-1), p]}

最后，设正向路径a: a0 = 0 < a1 < a2 ... < ap = n, 逆向路径b: bq = n > b(q-1) ... > b0 = 0,
则要求的最短路程为:
w = min{sum(k = 0 to p-2){d[a(k), a(k+1)]} + sum(k = 0 to q-2){d[b(k), b(k+1)]}
        + d[a(p-1), n] + d[b(q-1), n] }
由于路径a, b分别从0到n和从n到0, 故交换路径a和b不会对上述min中的值产生影响。
因此，不妨设经过点n-1的路径为a，则a(p-1) = n-1，于是
w = min{sum(k = 0 to p-2){d[a(k), a(k+1)]} + sum(k = 0 to q-2){d[b(k), b(k+1)]}
        + d[n-1, n] + d[b(q-1), n] }
  = d[n-1, n] +
    min{sum(k = 0 to p-2){d[a(k), a(k+1)]} + sum(k = 0 to q-2){d[b(k), b(k+1)]}
        + d[b(q-1), n]}
  = d[n-1, n] + min(b(q-1) = 0 to n-2){ w(n-1, b(q-1)) + d[b(q-1), n] }

总结一下：
w(1, 0) = d[1, 0];
w(p, q) =
 (q < p-1) -> d[p-1, p] + min(b(j-1) = 0 to q-1){w(p-1, b(j-1)) + d[b(j-1), q]};
 (q = p-1) -> min(a(i-1) = 0 to p-2){w(p-1, a(i-1)) + d[a(i-1), p]};
w = d[n-1, n] + min(b(q-1) = 0 to n-2){ w(n-1, b(q-1)) + d[b(q-1), n] }

由于构造w(p, q)需要知道w(p-1, j) where 0 <= j < p-1，
所以指定构造顺序为：
for (p = 1 to n-1)
  for (q = 0 to p-1)
    compute w(p, q);
compute w;

复杂度：
sum(p = 1 to n-1){ sum(q = 0 to p-1) {q} }
= n(n-1)^2 / 6
= O(n^3)