[Leetcode 1066] Campus Bikes II

原题说明

On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

Example 1:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: 6
Explanation: 
We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.

Example 2:

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: 4
Explanation: 
We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.

Note:

0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
All worker and bike locations are distinct.
1 <= workers.length <= bikes.length <= 10

解题思路

我们先用一个二维矩阵记录每个工人到每辆车的距离，dp[i][j] = distance就表示工人i和车j的距离为distance。

这样我们把问题就转化为：在二维矩阵里每一行取一个数，同时每个数不能有相同的列，要求让所有取出的数之和最小。

如果用简单的暴力破解，用dfs把所有取法都遍历一遍，时间复杂度是O(N!)。这里是不能通过测试的。

因此我们需要用backtracking + memoization的方法做优化。用一个数state表示已经选取了的bike的组合。这样memo[state]就表示在当前选取的自行车组合下，之后能得到的最小和。

这样我们就能从后往前递归，减少重复计算的，大大降低时间复杂度。
这是一种bottom up的思想。

这里有一个技巧，我们用二进制的思想构造state。因为自行车的数量不超过10个,那么在第i位上，如果等于1，则说明第i辆自行车被选择了，否则就是没被选择。

示例代码 (cpp)

class Solution {
private:
    int dict(const vector<int>& worker, const vector<int>& bike) {
        return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1]);
    }
    public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        vector<vector<int>> dp(workers.size(), vector<int>(bikes.size(), 0));
        for (auto i = 0; i < workers.size(); ++i) {
            for (auto j = 0; j < bikes.size(); ++j) {
                dp[i][j] = dict(workers[i], bikes[j]);
            }
        }
        int res = INT_MAX;
        vector<int> memo(1 << bikes.size(), 0);
        return permRes(dp, memo, 0, 0);
    }
    int permRes(const vector<vector<int>>& dp, 
                vector<int>& memo, 
                int state, 
                int idx) 
    {
        if (idx == dp.size()) {
            return 0;
        }
        if (memo[state] != 0) {
            return memo[state];
        }
        int tmp = INT_MAX;
        for (auto j = 0; j < dp[0].size(); j++) {
            if ((state & (1 << j)) == 0) {
                tmp = min(tmp, dp[idx][j] + permRes(dp, memo, state | (1<<j), idx + 1));
            }
        }
        memo[state] = tmp;
        return memo[state];
    }
};

示例代码 (java)

class Solution {
    public int assignBikes(int[][] workers, int[][] bikes) {
        int[] dp = new int[1 << bikes.length];
        return dfs(workers, bikes, 0, 0, dp);
    }
    private int dfs(int[][] w, int[][] b, int idx, int used, int[] dp) {
        if (idx == w.length) return 0;
        if (dp[used] > 0) return dp[used];
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < b.length; i++) {
            if ((used & (1 << i)) != 0) continue;
            res = Math.min(res, Math.abs(w[idx][0] - b[i][0]) + Math.abs(w[idx][1] - b[i][1])
                       + dfs(w,b,idx + 1, used | (1<<i), dp));
        }
        return dp[used] = res;
    }
}

示例代码 (python)

class Solution:
    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
        dic = {}
        
        def helper(a,b):
            return abs(a[0] - b[0]) + abs(a[1] - b[1])
        
        def dfs(p, arr):
            if p == len(workers):
                return 0
            if (p, tuple(arr)) in dic:
                return dic[(p, tuple(arr))]
            temp = float('inf')
            for i in range(len(arr)):
                if arr[i] == 0:
                    temp = min(temp,  helper(bikes[i], workers[p]) + dfs(p + 1, arr[:i] + [1] + arr[i + 1:]))
            dic[(p, tuple(arr))] = temp
            return temp
        
        ans = dfs(0, [0 for _ in range(len(bikes))])
        return ans

复杂度分析

M为workers数量，N为bikes数量
时间复杂度: state一共有2^N,每个state至多被计算一遍，因此这里是O(2^N)
空间复杂度: 距离的cache可以忽略不计，主要开销在memo上，因此这里是O(2^N)

视频讲解

我们在Youtube上更新了视频讲解，欢迎关注！