最適ペアリング問題(集合上の動的計画)――状圧DP

テーマ:紫書P 284
タイトル:
n個の点の空間座標(nは偶数で、n<=20)を与えて、彼らをn/2対に配合して、どのようにペアリングして点対の距離と最小にすることができますか? 
問題:
dp[s]を、状態がs(sはあるサブセットを表す)の場合の最小距離和とする.
1.1つの状態sについて、まず、2つの点を減らした状態の最小距離和を計算し、その後、現在の状態がこれらの状態から移行する.
2.どのように移行するか:状態sについて、集合の中で任意に1つの点を探して、集合の中の他の点を列挙してそれとペアを組んで、距離と最小のペアを取ります.
3.なぜ1つの点を選択し、集合内の他の点を列挙すればよいのでしょうか.どちらの点も列挙しますか?なぜなら、選択した点に対して、集合内の他の点とペアを組まなければならないので、答えはあるペアに隠されているに違いありません.2つの点を列挙すると、実際には余計です.
実装:
1.繰返し:下から上へ、最小のサブセットから計算を開始し、大きなサブセットを転送できます.欠点は点数が奇数の場合も考慮に入れ(点数が偶数かどうかを予め判断して計算に入る必要があるかどうかを決めることができる)、速度が遅い.
2.記憶化探索:状態sについて、偶数サブセットの最小距離和が計算されたと仮定すると、ある点を選択し、他の点を列挙すればよい.また、奇数要素のサブセットの計算は回避されます.
プッシュ:

#include 
#include 
#include 
using namespace std;
const int INF = 2e9;
const int maxn = 21;

struct Node{
    double x, y, z;
}dot[maxn];

int n;
double dp[1<> n;
    for(int i = 0; i < n; i++)
        cin >> dot[i].x >> dot[i].y >> dot[i].z;

    solve();
    cout << dp[(1<

メモリ検索:

#include 
#include 
#include 
using namespace std;
const int INF = 2e9;
const int maxn = 21;

struct Node{
    double x, y, z;
}dot[maxn];

int n;
double dp[1<> n;
    for(int i = 0; i < n; i++)
        cin >> dot[i].x >> dot[i].y >> dot[i].z;

    dp[0] = 0;
    for(int i = 1; i < (1<