f (subset, last)
для динамики:
порядок уже посещённых не важен
важна только последняя вершина

f (subset, last) = min (prev)
                       {f (subset \ {last}, prev) + dist (prev, last)}


Пример:
   s=vvv
f ({2, 4, 5, 6}, last=5) = min
                             f ({2, 4, 6}, last=6) + dist (6, 5)
                             f ({2, 4, 6}, last=4) + dist (4, 5)
                             f ({2, 4, 6}, last=2) + dist (2, 5)
                                t=^^^

for (int s = 0; s < m; s++)
  for (int last = 0; last < n; last++) if (s & (1 << last)) {
    int t = s - (1 << last);
    for (int prev = 0; prev < n; prev++) if (t & (1 << prev))
      f[s][last] = min (f[s][last], f[t][prev] + dist[prev][last]);
  }

Время: 2^n * n^2
Память: 2^n * n