1066

class Solution {
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int wlen = workers.size(), blen = bikes.size();
        vector<vector<int>> memo(wlen, vector(1<<blen, -1));
        return solve(workers, bikes, wlen, blen, memo, 0, 0);
    }

    int solve(vector<vector<int>>& workers, vector<vector<int>>& bikes, int wlen, int blen, vector<vector<int>>& memo, int pos, int mask){
        if(pos == wlen) return 0;
        if(memo[pos][mask] != -1) return memo[pos][mask];
        int ans = INT_MAX;
        for(int i=0; i<blen; i++){
            if((mask & (1<<i)) == 0){
               ans = min(ans, solve(workers, bikes, wlen, blen, memo, pos+1, mask|(1<<i))+getDist(workers[pos], bikes[i]));
            }
        }
        return memo[pos][mask] = ans;
    }

    int getDist(vector<int> &a, vector<int> &b){
        return int(abs(a[0]-b[0])+abs(a[1]-b[1]));
    }
};

-----------------------

class Solution {
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int wlen = workers.size(), blen = bikes.size();
        vector<int> memo(1<<blen, -1);
        return solve(workers, bikes, wlen, blen, memo, 0, 0);
    }

    int solve(vector<vector<int>>& workers, vector<vector<int>>& bikes, int wlen, int blen, vector<int>& memo, int pos, int mask){
        // Base case when we have assigned bikes to all workers.
        if(pos == wlen) return 0;

        // Check if the state is already visited.
        if(memo[mask] != -1) return memo[mask];

        int ans = INT_MAX;
        // Check if current bike is free, if yes, assign it to current worker, set bit and move on.
        for(int i=0; i<blen; i++){
            if((mask & (1<<i)) == 0){
               ans = min(ans, solve(workers, bikes, wlen, blen, memo, pos+1, mask|(1<<i))+getDist(workers[pos], bikes[i]));
            }
        }

        // Update cache and return.
        return memo[mask] = ans;
    }

    int getDist(vector<int> &a, vector<int> &b){
        return int(abs(a[0]-b[0])+abs(a[1]-b[1]));
    }
};