Problem statement

https://leetcode.com/problems/campus-bikes-ii/

Solution

Straightforward bit-dp problem, where dp(mask, i) means that we have mask of avaliable bikes and i is index of current worker we want to distribute bike to. To evaluate value we need to check all non-zero bytes in mask and check value dist(W[i], B[j]) + dp(mask^(1<<j), i-1) for them.

Complexity

Time complexity is O(2^m*m), because we have at most 2^m states: even though we have (mask, i), in fact number of non-zero bits in mask minus i is constant (equal to m-n+1). And we have O(m) transactions from one state to others. Space complexity is O(2^m).

Code

class Solution:
    def assignBikes(self, W, B):
        def dist(A, B):
            return abs(A[0] - B[0]) + abs(A[1] - B[1])

        @lru_cache(None)
        def dp(mask, i):
            if i == -1: return 0
            return min(dist(W[i], B[j]) + dp(mask^(1<<j), i-1) for j in range(m) if (mask>>j) & 1)

        n, m = len(W), len(B)
        return dp((1<<m)-1, n-1)