Shortest Delivery Tour
Hard · rating 2100 · Dynamic Programming, Bitmask
A courier must start at city 0, visit every city exactly once, and return to 0. The first line has n. The next n lines form an n × n distance matrix. Print the length of the shortest such round trip.
Constraints: 1 ≤ n ≤ 10
Editorial
Approach
The travelling-salesman tour is exponential to brute-force, but Held–Karp dynamic programming solves it in O(2ⁿ · n²). Let dp[mask][u] be the cheapest path that starts at city 0, visits exactly the cities in mask, and ends at u. Extend each state by one unvisited city.
Closing the loop
Once mask is the full set, add the edge back to city 0 from each possible last city and take the minimum.
dp[1][0] = 0
for mask in range(1<Complexity
Time: O(2ⁿ · n²). Space: O(2ⁿ · n).
Related problems
- Longest Valid Parentheses — Hard
- Longest Common Substring — Hard
- Maximal Square — Hard
- Balanced Bracket Count — Hard
- Equal Subset Partition — Hard
- Treasure Grid — Hard