What is the main challenge in Minimum Cost to Connect Two Groups of Points?

The key challenge is ensuring each point in both groups is connected at least once while minimizing total cost, using state transition DP.

How does bitmasking help in this problem?

Bitmasking allows efficient representation of subsets of second-group points already connected, enabling quick DP state transitions and cost updates.

Can multiple first-group points connect to the same second-group point?

Yes, multiple first-group points can connect to the same second-group point without additional restrictions; the goal is minimal total cost.

What is the time complexity of the DP approach?

The time complexity is O(size1 * 2^size2 * size2) because for each first-group point we iterate over all subsets of second-group points and all possible connections.

Is this problem always solvable for size1 >= size2?

Yes, as long as size1 >= size2, a solution exists since DP can always assign connections to cover all points efficiently.

#1595

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

连通两组点的最小成本

给你两组点，其中第一组中有 size 1 个点，第二组中有 size 2 个点，且 size 1 >= size 2 。任意两点间的连接成本 cost 由大小为 size 1 x size 2 矩阵给出，其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。如果两个组中…

数组动态规划位运算矩阵位掩码

题目描述

给你两组点，其中第一组中有 size₁ 个点，第二组中有 size₂ 个点，且 size₁ >= size₂ 。

任意两点间的连接成本 cost 由大小为 size₁ x size₂ 矩阵给出，其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。

返回连通两组点所需的最小成本。

示例 1：

输入：cost = [[15, 96], [36, 2]]
输出：17
解释：连通两组点的最佳方法是：
1--A
2--B
总成本为 17 。

示例 2：

输入：cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
输出：4
解释：连通两组点的最佳方法是：
1--A
2--B
2--C
3--A
最小成本为 4 。
请注意，虽然有多个点连接到第一组中的点 2 和第二组中的点 A ，但由于题目并不限制连接点的数目，所以只需要关心最低总成本。

示例 3：

输入：cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
输出：10

提示：

size₁ == cost.length
size₂ == cost[i].length
1 <= size₁, size₂ <= 12
size₁ >= size₂
0 <= cost[i][j] <= 100

lightbulb

解题思路

方法一：状态压缩 + 动态规划

我们记第一组的点数为 $m$ ，第二组的点数为 $n$ 。

由于 $1 \leq n \leq m \leq 12$ ，因此，我们可以用一个整数来表示第二组中点的状态，即二进制表示的一个长度为 $n$ 的整数，其中第 $k$ 位为 $1$ 表示第二组中的第 $k$ 个点与第一组中的点连通，为 $0$ 表示不连通。

接下来，我们定义 $f[i][j]$ 表示第一组中的前 $i$ 个点已经全部连通，且第二组中的点的状态为 $j$ 时的最小成本。初始时 $f[0][0] = 0$ ，其余值均为正无穷大。答案即为 $f[m][2^n - 1]$ 。

考虑 $f[i][j]$ ，其中 $i \geq 1$ 。我们可以枚举第二组中的每个点 $k$ ，如果点 $k$ 与第一组中的第 $i$ 个点连通，那么我们可以分以下两种情况讨论：

如果点 $k$ 只与第一组中的第 $i$ 个点连通，那么 $f[i][j]$ 可以从 $f[i][j \oplus 2^k]$ 或者 $f[i - 1][j \oplus 2^k]$ 转移而来，其中 $\oplus$ 表示异或运算；
如果点 $k$ 与第一组中的第 $i$ 个点以及其他点都连通，那么 $f[i][j]$ 可以从 $f[i - 1][j]$ 转移而来。

在上述两种情况中，我们需要选择转移值最小的那个，即有：

f[i][j] = \min_{k \in \{0, 1, \cdots, n - 1\}} \{f[i][j \oplus 2^k], f[i - 1][j \oplus 2^k], f[i - 1][j]\} + cost[i - 1][k]

最后，我们返回 $f[m][2^n - 1]$ 即可。

时间复杂度 $O(m \times n \times 2^n)$ ，空间复杂度 $O(m \times 2^n)$ 。其中 $m$ 和 $n$ 分别是第一组和第二组中的点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        m, n = len(cost), len(cost[0])
        f = [[inf] * (1 << n) for _ in range(m + 1)]
        f[0][0] = 0
        for i in range(1, m + 1):
            for j in range(1 << n):
                for k in range(n):
                    if (j >> k & 1) == 0:
                        continue
                    c = cost[i - 1][k]
                    x = min(f[i][j ^ (1 << k)], f[i - 1][j], f[i - 1][j ^ (1 << k)]) + c
                    f[i][j] = min(f[i][j], x)
        return f[m][-1]

speed

复杂度分析

指标	值
时间	complexity is O(size1 * 2^size2 * size2), as we process each first-group point and all subsets of second-group points. Space complexity is O(2^size2) if optimizing with a rolling DP array, otherwise O(size1 * 2^size2) for a full DP table.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expecting knowledge of state transition DP with bitmask representation
question_mark
Looking for correct handling of subsets and connection coverage
question_mark
Watch for optimization by reducing unnecessary DP updates

warning

常见陷阱

外企场景

error
Forgetting that each second-group point must be connected at least once
error
Incorrectly updating DP without considering previous masks
error
Overlooking that multiple first-group points can connect to the same second-group point without extra cost

swap_horiz

进阶变体

外企场景

arrow_right_alt
Connection cost matrix may be asymmetric or contain zeros
arrow_right_alt
Number of points in groups can be equal or have first group larger
arrow_right_alt
Cost limits can vary, requiring careful handling of maximum sums

help

常见问题

外企场景

继续练习

#1349 参加考试的最大学生数 #1655 分配重复整数 #1681 最小不兼容性