连通两组点的最小成本

难度: Hard

给你两组点，其中第一组中有 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

Submission

运行时间: 371 ms

内存: 16.0 MB

class Solution:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        f = [0] * (1 << len(cost[0]))
        for j, mn in enumerate(map(min, zip(*cost))):
            bit = 1 << j
            for mask in range(bit):
                f[bit | mask] = f[mask] + mn
        for row in cost:
            for j in range(len(f) - 1, -1, -1):
                f[j] = min(f[j & ~(1 << k)] + c for k, c in enumerate(row))
        return f[-1]

Explain

这道题本质上是一个最小成本完全匹配问题，可以通过动态规划的方式解决。动态规划数组 `f` 的大小为 `1 << size2`，代表第二组中的点的所有可能的连接状态。每个位对应一个点，若该位为1，则表示对应的点已被连接。\n\n1. 初始化 `f` 数组，其中 `f[0]` 为0，表示没有点被连接的状态。对于每个点j，计算如果仅连接该点的最小成本，更新 `f` 数组中对应状态的值。\n2. 针对第一组中的每个点，更新 `f` 数组。对于每一个已有的状态 `j`，遍历第二组中的所有点，并尝试将当前的点与第二组中的每个点相连接，更新状态。\n3. 最终，`f[-1]` 即包含所有第二组点都被连接的状态，其值为所需的最小成本。

时间复杂度: O(size1 * size2 * 2^size2)

空间复杂度: O(2^size2)

class Solution:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        # 动态规划数组, 大小为2^size2
        f = [float('inf')] * (1 << len(cost[0]))
        f[0] = 0
        # 初始化只连接一个点的情况
        for j, mn in enumerate(map(min, zip(*cost))):
            bit = 1 << j
            for mask in range(bit):
                f[bit | mask] = min(f[bit | mask], f[mask] + mn)
        # 更新所有点的连接状态
        for row in cost:
            new_f = [float('inf')] * (1 << len(cost[0]))
            for j in range(len(f)):
                # 尝试将当前行的点与第二组中的每个点连接
                for k, c in enumerate(row):
                    new_f[j | (1 << k)] = min(new_f[j | (1 << k)], f[j] + c)
            f = new_f
        # 返回所有第二组点都被连接的最小成本
        return f[-1]

Explore

在这个动态规划解法中，数组`f`的每个索引是一个整数，这个整数的二进制表示形式用于表示第二组中点的连接状态。这里的每个位代表对应序号的点是否已经被连接。如果某一位为1，那么表示对应的点已经被连接；如果为0，则表示对应的点尚未连接。例如，索引为5（二进制为0101）表示第二组中第0位和第2位的点已被连接，而第1位和其他位的点尚未连接。

初始化动态规划数组`f`时，`f[0]`设为0表示一开始没有任何点被连接的状态，其成本为0。其他所有值初设为无穷大（`float('inf')`）是为了在后续的动态规划过程中，通过比较和更新来找到实际可达的最小成本。这样做确保了只有那些通过实际操作可以达到的状态（即连接某些点的组合）才会被更新为较小的成本值，未被实际访问的状态成本保持无穷大，表示不可达。

在解法中，尝试将当前行（即第一组中的某个点）与第二组中的每个点连接的过程是通过嵌套循环实现的。对于每个已存在的状态`j`（表示已经有一些第二组的点被连接的状态），再遍历第二组中的每个点的索引`k`。对于每个点`k`，通过`j | (1 << k)`这个操作来生成一个新状态，这个新状态表示在原有的连接状态基础上再连接第`k`个点。接着，更新`f[j | (1 << k)]`的值，这个值是通过比较原状态`f[j]`加上连接点`k`的额外成本`c`与当前`f[j | (1 << k)]`的值，选择其中的较小值来实现的。这个过程确保了每个连接组合的最小成本都被计算和更新。

在动态规划中，单独处理只连接一个点的情况是为了建立基础状态，这可以看作是对动态规划数组`f`的初始化优化。通过计算每个单独点的最小连接成本，并更新对应的`f`数组状态，我们可以确保在开始处理复杂的多点连接状态之前，每个单点连接的最优解已经被考虑。这样做可以简化后续的计算，因为复杂的状态（连接多个点的状态）可以通过比较和组合这些基础的单点最优解来构建，从而优化整体解决方案的效率和准确性。