Held-Karp DP defines dp[mask][u] as minimum cost to start at source, visit mask, and finish at u. Transitions add one new city at a time. Exact but exponential in n, significantly better than plain factorial enumeration.
int tspDP(vector<vector<int>>& c) {
int n = c.size(), N = 1 << n, INF = 1e9;
vector<vector<int>> dp(N, vector<int>(n, INF));
dp[1][0] = 0;
for (int mask = 1; mask < N; mask++) {
for (int u = 0; u < n; u++) if (dp[mask][u] < INF) {
for (int v = 0; v < n; v++) if (!(mask & (1 << v))) {
int nmask = mask | (1 << v);
dp[nmask][v] = min(dp[nmask][v], dp[mask][u] + c[u][v]);
}
}
}
int ans = INF;
for (int u = 1; u < n; u++) ans = min(ans, dp[N - 1][u] + c[u][0]);
return ans;
}mask encodes visited set; endpoint u closes subproblem state.
Extend path from u to unvisited city v and update new mask.
Exponential but much better than factorial brute force.
Quiz coming soon for this algorithm.