leetcode 1066 状态压缩DP

问题

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:

img

1
2
3
4
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:

img

1
2
3
4
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:

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

分析

思路1: 使用DFS，时间复杂度达到阶乘 $O(m!)$ ，导致超时。

思路2: 使用状态压缩的dp，对bikes分配的情况进行二进制状态压缩，如 s = 0'b00000001 表示下标为 $0$ 的bikes已经被分配， s = 0'b00011101 表示下标为0，2，3，4的bikes被分配。$dp[i][s]$ 表示前 $i$ 个work分配状态为 $s$ 时的最小距离。 要求 $dp[i][s]$ 可以假设 $s$ 的二进制中每一位可能是最别被分配给第 $i$ 个work的情况，然后求出所有情况的最小值。
$$
dp[i][s] = min(dp[i][s], dp[i][prev] + dis(work[i-1], bike[j])) \;((1<<j)\&s \neq 0 \; \&\& \; prev = s \oplus(1<<j))
$$
其中 $ 0 \leq j < m$ 。

初始 $dp[0][0] = 0$，其他为 $INT$

目标 $min(dp[n][x])$. (不和要求的状态都会为 $INT$).

代码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
class Solution {
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int ans = INT_MAX;
        vector<bool> v(bikes.size(), false);
        dfs(ans, 0, workers, bikes, v, 0);
        return ans;
    }

    void dfs(int &ans, int cur, vector<vector<int>>& workers, vector<vector<int>>& bikes, vector<bool> &v, int i) {
        if (i >= workers.size()) {
            ans = min(cur, ans);
            return;
        }
        if (cur >= ans) return;
        for (int j = 0; j < bikes.size(); ++j) {
            if (v[j] == true) continue;
            int dis = abs(workers[i][0]-bikes[j][0]) + abs(workers[i][1]-bikes[j][1]);
            v[j] = true;
            dfs(ans, cur+dis, workers,bikes, v, i+1);
            v[j] = false;
        }
    }
};

代码2

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
35
36
37
38
39
40
41
// 状态压缩DP
class Solution {
public:
    int dis(vector<int>& a, vector<int>& b) {
        return abs(a[0]-b[0]) + abs(a[1]-b[1]);
    }
    // inline int countOne(int x) {
    //     int ans = 0;
    //     while (x > 0) {
    //         ans += x&0x01;
    //         x >>= 1;
    //     }
    //     return ans;
    // }
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int n = workers.size();
        int m = bikes.size();
        vector<vector<int>> dp(n+1, vector<int>(1<<m, 0x3f3f3f3f));
        vector<int> count(1<<m, 0);

        dp[0][0] = 0;
        int ans = INT_MAX;
        for (int i = 1; i <= n; ++i) {
            for (int s = 0; s < (1<<m); ++s) {
                if (__builtin_popcount(s) != i) continue;  
                // if (countOne(s) != i) continue;
                // 使用前28ms 使用之后 4ms，内建的和自己写的都差不多
                for (int j = 0; j < m; ++j) {
                    if ((1<<j) & s) {
                        int prev = s^(1<<j);
                        dp[i][s] = min(dp[i][s], dp[i-1][prev] + dis(workers[i-1], bikes[j]));
                    }
                }
                if (i == n) {
                    ans = min(ans, dp[i][s]);
                }
            }
        }
        return ans;
    }
};