https://leetcode.com/problems/minimum-cost-to-connect-two-groups-of-points/ from Google

My intuition for this is: greedly picking the cheapest cost which can expand at least one point, and continue this until we reach out to all points. However, this doesn’t work since it’s possible that using a second best cost will result in a better global cost (I realized this after implementing this and got a wrong answer in the contest…). Then, I tried exhausted search, which basically tried all the combination of the edges. This can work but the time complexity is too big. In the worst case, we have 12*12=144 edges, and to search all of them will result in an O(2^144) time complexity. Although I tried to prune the search space on the fly and managed to past 70 test cases, but still ended up getting a TLE (even after I memorized all the partial solutions…).

The working solution for this is like below. I still need to cache the partial solutions, and I still need to use backtracking (this is a top-down solution, which I think is more straightforward to me). The difference is: I shouldn’t try all the combination of edges. I should try to reduce this by determining one node first, and then work on the sub-problem again … and so on. Another caveat is that once we lock down all the left side nodes, we shouldn’t re-do the same process for the right side nodes as we can just pick the cheapest edges to cover them and that’s all.

Finally, use a bit masks to memorize the partial solution. We don’t need a bit mask for left side nodes. I did this just because my previous needs that, and I’m too lazy to re-write it…

 1class Solution {
 2public:
 3    int L, R;
 4    vector<vector<int>> dp;
 5    int ans;
 6    int dfs(vector<vector<int>>& lE, int lS, vector<int>& rE, int rS, int cur) {
 7        if (dp[lS][rS]) {
 8            return dp[lS][rS];
 9        }
10        if (lS == ((1<<L)-1) and rS == ((1<<R)-1)) {
11            return 0;
12        }
13        int ret = INT_MAX-2400;
14        if (lS < ((1<<L)-1)) {
15            int i = cur;
16            for (int j=0; j<R; j++) {
17                ret = min(ret, lE[i][j]+dfs(lE, lS|(1<<i), rE, rS|(1<<j), cur+1));
18            }
19        } else {
20            ret = 0;
21            for (int i=0; i<R; i++) {
22                if (((1<<i)&rS) == 0) {
23                    ret += rE[i];
24                }
25            }
26        }
27        return dp[lS][rS] = ret;
28    }
29    int connectTwoGroups(vector<vector<int>>& cost) {
30        L = cost.size();
31        R = cost[0].size();
32        dp.resize((1<<L), vector<int>((1<<R)));
33        vector<int> r2l(R, INT_MAX);
34        ans = INT_MAX;
35        for (int i=0; i<L; i++) {
36            for (int j=0; j<R; j++) {
37                r2l[j] = min(r2l[j], cost[i][j]);
38            }
39        }
40        int ls=0, rs=0, cur=0;
41        return dfs(cost, ls, r2l, rs, cur);
42    }
43};