DP_TSP.java

memo = new int[V][1 << V];
T = new int[V][V]; // adjacency matrix
int min_dist_from_0 = DP_TSP(0, 1);

int DP_TSP(int u, int m) { // m is visited mask (bitmask)
	if (m == ((1 << V) - 1)) // all 1, all vertices have been visited
		return T[u][0]; // no choice, return to vertex 0
	if (memo[u][m] != -1) // computed before
		return memo[u][m];

	memo[u][m] = INF; // general case

	for (int v = 0; v < V; v++) { // for each v in V
		if ((m & (1 << v)) == 0) { // if v is not turned on
			memo[u][m] = Math.min(memo[u][m],
				T[u][v] + DP_TSP(v, m | (1 << v))); // weight[u][v] + DP_TSP(v, m with v-th bit turned on)
		}
	}
	return memo[u][m];
}