# 1066. Campus Bikes II

• Time: $O(m \cdot 2^m)$
• Space: $O(2^m)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public: int assignBikes(vector>& workers, vector>& bikes) { // dp[i] := min dist to assign bikes j (bitmask) dp.resize(1 << bikes.size()); return assignBikes(workers, bikes, 0, 0); } private: vector dp; int assignBikes(const vector>& workers, const vector>& bikes, int s, int bikeUsed) { if (s == workers.size()) return 0; if (dp[bikeUsed]) return dp[bikeUsed]; int ans = INT_MAX; for (int i = 0; i < bikes.size(); ++i) { if (bikeUsed >> i & 1) continue; ans = min(ans, dist(workers[s], bikes[i]) + assignBikes(workers, bikes, s + 1, bikeUsed | 1 << i)); } return dp[bikeUsed] = ans; } int dist(const vector& p1, const vector& p2) { return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public int assignBikes(int[][] workers, int[][] bikes) { // dp[i] := min dist to assign bikes j (bitmask) dp = new int[1 << bikes.length]; return assignBikes(workers, bikes, 0, 0); } private int[] dp; private int assignBikes(int[][] workers, int[][] bikes, int s, int bikeUsed) { if (s == workers.length) return 0; if (dp[bikeUsed] > 0) return dp[bikeUsed]; int ans = Integer.MAX_VALUE; for (int i = 0; i < bikes.length; ++i) { if ((bikeUsed >> i & 1) == 1) continue; ans = Math.min(ans, dist(workers[s], bikes[i]) + assignBikes(workers, bikes, s + 1, bikeUsed | 1 << i)); } return dp[bikeUsed] = ans; } private int dist(int[] p1, int[] p2) { return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int: def dist(p1: List[int], p2: List[int]) -> int: return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]) # Dp(s, j) := min dist to assign bikes j (bitmask) to workers[s:] @functools.lru_cache(None) def dp(s: int, bikeUsed: int) -> int: if s == len(workers): return 0 ans = math.inf for i, bike in enumerate(bikes): if bikeUsed >> i & 1: continue ans = min(ans, dist(workers[s], bike) + dp(s + 1, bikeUsed | 1 << i)) return ans return dp(0, 0)