Skip to content

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

 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)