State
dp[mask][i] = min cost to visit cities in mask ending at i.
Advertisement
Transition
for (int mask = 1; mask < (1 << n); mask++)
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0) continue;
for (int j = 0; j < n; j++) {
if (j == i || (mask & (1 << j)) == 0) continue;
dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + dist[j][i]);
}
}Advertisement
Answer
min over i of dp[(1<
Complexity
O(2^N × N²) time, O(2^N × N) space. Practical for N ≤ 20.