Hard

题目描述

给你两组点，第一组有 size1 个点，第二组有 size2 个点，其中 size1 >= size2。

任意两点间的连接成本由一个 size1 x size2 的矩阵 cost 给出，其中 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

约束:

  • size1 == cost.length
  • size2 == cost[i].length
  • 1 <= size1, size2 <= 12
  • size1 >= size2
  • 0 <= cost[i][j] <= 100

解题思路

这是一个经典的状态压缩动态规划问题。核心思路是使用位掩码来表示第二组点的连接状态。

思路分析：

  1. 状态设计：由于第二组点数较少（≤12），我们可以用位掩码表示哪些第二组的点已被连接。定义 dp[i][mask] 表示处理了前 i 个第一组的点，第二组的连接状态为 mask 时的最小成本。

  2. 状态转移：对于第一组的第 i 个点，我们需要至少连接第二组的一个点。遍历所有可能的连接方案（可以连接多个点），更新对应的状态。

  3. 优化策略：为了确保第二组的每个点都被连接，在处理完所有第一组的点后，我们还需要考虑补充连接那些未被连接的第二组点。对于每个未连接的第二组点，选择连接成本最小的第一组点。

  4. 边界处理：初始状态 dp[0][0] = 0，其他状态初始化为无穷大。最终答案是所有 dp[size1][mask] 中 mask 覆盖所有第二组点的最小值。

算法步骤：

  • 预处理：计算每个第二组点连接到第一组的最小成本
  • 状态转移：枚举每个第一组点的连接方案
  • 最终补充：确保第二组每个点都被连接

代码实现

class Solution {
public:
    int connectTwoGroups(vector<vector<int>>& cost) {
        int m = cost.size(), n = cost[0].size();
        
        // 预处理：计算第二组每个点连接到第一组的最小成本
        vector<int> minCost(n, INT_MAX);
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                minCost[j] = min(minCost[j], cost[i][j]);
            }
        }
        
        // dp[i][mask] 表示处理前i个第一组点，第二组连接状态为mask的最小成本
        vector<vector<int>> dp(m + 1, vector<int>(1 << n, INT_MAX));
        dp[0][0] = 0;
        
        for (int i = 0; i < m; i++) {
            for (int mask = 0; mask < (1 << n); mask++) {
                if (dp[i][mask] == INT_MAX) continue;
                
                // 枚举第i个第一组点的连接方案
                for (int subset = 1; subset < (1 << n); subset++) {
                    int newMask = mask | subset;
                    int addCost = 0;
                    
                    for (int j = 0; j < n; j++) {
                        if (subset & (1 << j)) {
                            addCost += cost[i][j];
                        }
                    }
                    
                    dp[i + 1][newMask] = min(dp[i + 1][newMask], dp[i][mask] + addCost);
                }
            }
        }
        
        // 确保第二组每个点都被连接
        int ans = INT_MAX;
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[m][mask] == INT_MAX) continue;
            
            int totalCost = dp[m][mask];
            for (int j = 0; j < n; j++) {
                if (!(mask & (1 << j))) {
                    totalCost += minCost[j];
                }
            }
            ans = min(ans, totalCost);
        }
        
        return ans;
    }
};

class Solution:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        m, n = len(cost), len(cost[0])
        
        # 预处理：计算第二组每个点连接到第一组的最小成本
        min_cost = [min(cost[i][j] for i in range(m)) for j in range(n)]
        
        # dp[i][mask] 表示处理前i个第一组点，第二组连接状态为mask的最小成本
        dp = [[float('inf')] * (1 << n) for _ in range(m + 1)]
        dp[0][0] = 0
        
        for i in range(m):
            for mask in range(1 << n):
                if dp[i][mask] == float('inf'):
                    continue
                
                # 枚举第i个第一组点的连接方案
                for subset in range(1, 1 << n):
                    new_mask = mask | subset
                    add_cost = sum(cost[i][j] for j in range(n) if subset & (1 << j))
                    dp[i + 1][new_mask] = min(dp[i + 1][new_mask], dp[i][mask] + add_cost)
        
        # 确保第二组每个点都被连接
        ans = float('inf')
        for mask in range(1 << n):
            if dp[m][mask] == float('inf'):
                continue
            
            total_cost = dp[m][mask]
            for j in range(n):
                if not (mask & (1 << j)):
                    total_cost += min_cost[j]
            ans = min(ans, total_cost)
        
        return ans

public class Solution {
    public int ConnectTwoGroups(IList<IList<int>> cost) {
        int m = cost.Count, n = cost[0].Count;
        
        // 预处理：计算第二组每个点连接到第一组的最小成本
        int[] minCost = new int[n];
        for (int j = 0; j < n; j++) {
            minCost[j] = int.MaxValue;
            for (int i = 0; i < m; i++) {
                minCost[j] = Math.Min(minCost[j], cost[i][j]);
            }
        }
        
        // dp[i][mask] 表示处理前i个第一组点，第二组连接状态为mask的最小成本
        int[,] dp = new int[m + 1, 1 << n];
        for (int i = 0; i <= m; i++) {
            for (int mask = 0; mask < (1 << n); mask++) {
                dp[i, mask] = int.MaxValue;
            }
        }
        dp[0, 0] = 0;
        
        for (int i = 0; i < m; i++) {
            for (int mask = 0; mask < (1 << n); mask++) {
                if (dp[i, mask] == int.MaxValue) continue;
                
                // 枚举第i个第一组点的连接方案
                for (int subset = 1; subset < (1 << n); subset++) {
                    int newMask = mask | subset;
                    int addCost = 0;
                    
                    for (int j = 0; j < n; j++) {
                        if ((subset & (1 << j)) != 0) {
                            addCost += cost[i][j];
                        }
                    }
                    
                    dp[i + 1, newMask] = Math.Min(dp[i + 1, newMask], dp[i, mask] + addCost);
                }
            }
        }
        
        // 确保第二组每个点都被连接
        int ans = int.MaxValue;
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[m, mask] == int.MaxValue) continue;
            
            int totalCost = dp[m, mask];
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) == 0) {
                    totalCost += minCost[j];
                }
            }
            ans = Math.Min(ans, totalCost);
        }
        
        return ans;
    }
}

var connectTwoGroups = function(cost) {
    const size1 = cost.length;
    const size2 = cost[0].length;
    
    // Precompute minimum cost to connect each point in group 2
    const minCost = new Array(size2);
    for (let j = 0; j < size2; j++) {
        minCost[j] = Math.min(...cost.map(row => row[j]));
    }
    
    const memo = new Map();
    
    function dp(i, mask) {
        if (i === size1) {
            // Connect remaining unconnected points in group 2
            let cost = 0;
            for (let j = 0; j < size2; j++) {
                if (!(mask & (1 << j))) {
                    cost += minCost[j];
                }
            }
            return cost;
        }
        
        const key = `${i},${mask}`;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        let result = Infinity;
        
        // Try connecting point i to different subsets of group 2
        for (let subset = 1; subset < (1 << size2); subset++) {
            let subsetCost = 0;
            let newMask = mask;
            
            for (let j = 0; j < size2; j++) {
                if (subset & (1 << j)) {
                    subsetCost += cost[i][j];
                    newMask |= (1 << j);
                }
            }
            
            result = Math.min(result, subsetCost + dp(i + 1, newMask));
        }
        
        memo.set(key, result);
        return result;
    }
    
    return dp(0, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × 4^n)
空间复杂度O(m × 2^n)

说明：

  • 时间复杂度：外层循环 O(m)，内层状态数 O(2^n)，每个状态枚举子集 O(2^n)，总体 O(m × 4^n)
  • 空间复杂度：DP 数组大小为 O(m × 2^n)，加上辅助数组 O(n)，总体 O(m × 2^n)