Bitmask DP Essentials
Subset-state DP for TSP-style problems and assignment. Drills cover state encoding, transitions, and the precondition on `n`.
Question Bank
Hard
Python
bitmask-dp
dynamic-programming
algorithms
interview-prep
490 views
14
Implement TSP for n <= 20 cities with dp[mask][u] = shortest path that visits exactly the cities in mask and ends at u. Return the min Hamiltonian cycle cost starting and ending at city 0.
Examples
Example 1:
Input: dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
Output: 80
Explanation: dp[mask][u] = shortest path visiting cities in mask and ending at u. Base dp[1][0] = 0. Final answer is min over u != 0 of dp[full_mask][u] + dist[u][0]. Optimal tour 0 -> 1 -> 3 -> 2 -> 0 costs 10 + 25 + 30 + 15 = 80.5 more questions, with full solutions and explanations, are available for premium members.
Upgrade to Premium