## Campus Bikes II

• Time:O(m \cdot 2^m)
• Space:O(2^m)

## C++

class Solution {
public:
int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
// dp[i] := min dist to assign bikes j (bitmask)
dp.resize(1 << bikes.size());
return assignBikes(workers, bikes, 0, 0);
}

private:
vector<int> dp;

int assignBikes(const vector<vector<int>>& workers,
const vector<vector<int>>& 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<int>& p1, const vector<int>& p2) {
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]);
}
};


## JAVA

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]);
}
}


## Python

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:]
@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)