Skip to content

1595. Minimum Cost to Connect Two Groups of Points 👍

  • Time: $O(m \cdot 2^n \cdot n)$
  • Space: $O(m \cdot 2^n)$
 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
42
43
44
45
46
class Solution {
 public:
  int connectTwoGroups(vector<vector<int>>& cost) {
    const int m = cost.size();
    const int n = cost[0].size();
    // dp[i][j] := min cost to connect group1's points[i:] with group2's points
    // in mask j
    dp.resize(m, vector<int>(1 << n, -1));
    // minCosts[j] := min cost of connecting group2's point j
    vector<int> minCosts(n);

    for (int j = 0; j < n; ++j) {
      int minCostIndex = 0;
      for (int i = 1; i < m; ++i)
        if (cost[i][j] < cost[minCostIndex][j])
          minCostIndex = i;
      minCosts[j] = cost[minCostIndex][j];
    }

    return connect(cost, 0, 0, minCosts);
  }

 private:
  vector<vector<int>> dp;

  int connect(const vector<vector<int>>& cost, int i, int mask,
              const vector<int>& minCosts) {
    if (i == cost.size()) {
      // All points in group 1 are connected, so greedily assign the min cost
      // for the unconnected points of group2.
      int res = 0;
      for (int j = 0; j < cost[0].size(); ++j)
        if ((mask >> j & 1) == 0)
          res += minCosts[j];
      return res;
    }
    if (dp[i][mask] != -1)
      return dp[i][mask];

    int res = INT_MAX;
    for (int j = 0; j < cost[0].size(); ++j)
      res =
          min(res, cost[i][j] + connect(cost, i + 1, mask | 1 << j, minCosts));
    return dp[i][mask] = res;
  }
};

 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
42
class Solution {
  public int connectTwoGroups(List<List<Integer>> cost) {
    final int m = cost.size();
    final int n = cost.get(0).size();
    // dp[i][j] := min cost to connect group1's points[i:] with group2's points
    // in mask j
    dp = new Integer[m][1 << n];
    // minCosts[j] := min cost of connecting group2's point j
    int[] minCosts = new int[n];

    for (int j = 0; j < n; ++j) {
      int minCostIndex = 0;
      for (int i = 1; i < m; ++i)
        if (cost.get(i).get(j) < cost.get(minCostIndex).get(j))
          minCostIndex = i;
      minCosts[j] = cost.get(minCostIndex).get(j);
    }

    return connect(cost, 0, 0, minCosts);
  }

  private Integer[][] dp;

  private int connect(List<List<Integer>> cost, int i, int mask, int[] minCosts) {
    if (i == cost.size()) {
      // All points in group 1 are connected, so greedily assign the min cost
      // for the unconnected points of group2.
      int res = 0;
      for (int j = 0; j < cost.get(0).size(); ++j)
        if ((mask >> j & 1) == 0)
          res += minCosts[j];
      return res;
    }
    if (dp[i][mask] != null)
      return dp[i][mask];

    int res = Integer.MAX_VALUE;
    for (int j = 0; j < cost.get(0).size(); ++j)
      res = Math.min(res, cost.get(i).get(j) + connect(cost, i + 1, mask | 1 << j, minCosts));
    return dp[i][mask] = res;
  }
}

 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:
  def connectTwoGroups(self, cost):
    # minCosts[j] := min cost of connecting group2's point j
    minCosts = [min(col) for col in zip(*cost)]

    # dp(i, j) := min cost to connect group1's points[i:] with group2's points
    # in mask j
    @functools.lru_cache(None)
    def dp(i: int, mask: int) -> int:
      if i == len(cost):
        # All points in group 1 are connected, so greedily assign the min cost
        # for the unconnected points of group2.
        res = 0
        for j, minCost in enumerate(minCosts):
          if (mask >> j & 1) == 0:
            res += minCost
        return res

      res = math.inf
      for j in range(len(cost[0])):
        res = min(res, cost[i][j] + dp(i + 1, mask | 1 << j))
      return res

    return dp(0, 0)