Back to ChallengesDP with BitmaskingHard 45 min

DP with Bitmasking

Given a distance matrix of size N x N representing the distance between N cities (indexed 0 to N-1), find the minimum cost to visit all cities exactly once and return to the starting city (city 0).

Examples

Input: dist = [[0,20,42,25], [20,0,30,34], [42,30,0,10], [25,34,10,0]]

Output: 85

Optimal tour: 0 -> 1 -> 2 -> 3 -> 0. Cost = 20 + 30 + 10 + 25 = 85.

Constraints

• 1 <= N <= 15
• 0 <= dist[i][j] <= 1000
• dist[i][i] = 0

Complexity Analysis

Time

O(n^2 * 2^n)

states count is n * 2^n, and each transition takes O(n) time.

Space

O(n * 2^n)

storage table size for memoization.

Test Cases

#1 4 cities TSP

Input: [[0,20,42,25], [20,0,30,34], [42,30,0,10], [25,34,10,0]]

Expected: 85

#2 4 cities symmetric TSP

Input: [[0,10,15,20], [10,0,35,25], [15,35,0,30], [20,25,30,0]]

Expected: 80

JavaScript

Output

Click "Run Code" to see output here...