1595.连通两组点的最小成本

链接：1595.连通两组点的最小成本
难度：Hard
标签：位运算、数组、动态规划、状态压缩、矩阵
简介：给你两组点，其中第一组中有 size1 个点，第二组中有 size2 个点，且 size1 >= size2 。任意两点间的连接成本 cost 由大小为 size1 x size2 矩阵给出，其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。返回连通两组点所需的最小成本。

题解 1 - cpp

• 编辑时间：2023-06-20
• 执行用时：104ms
• 内存消耗：9.8MB
• 编程语言：cpp
• 解法介绍：dp[i][j]表示只有i个第一行元素的时候，已经使用了bitcount(j)个第二行元素时的最小开销。

class Solution {
public:
    int connectTwoGroups(vector<vector<int>>& cost) {
        int n = cost.size(), m = cost[0].size();
        vector<vector<int>>cache(n + 1, vector<int>(1 << m, 0x3f3f3f3f));
        cache[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int mask = 0; mask < (1 << m); mask++) {
                for (int j = 0; j < m; j++) {
                    if (mask & (1 << j)) {
                        cache[i][mask] = min(cache[i][mask], cache[i][mask & ~(1 << j)] + cost[i - 1][j]);
                        cache[i][mask] = min(cache[i][mask], cache[i - 1][mask] + cost[i - 1][j]);
                        cache[i][mask] = min(cache[i][mask], cache[i - 1][mask & ~(1 << j)] + cost[i - 1][j]);
                    }
                }
            }
        }
        return cache[n][(1 << m) - 1];
    }
};

题解 2 - python

• 编辑时间：2023-06-20
• 执行用时：1308ms
• 内存消耗：16.8MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        n = len(cost)
        m = len(cost[0])
        cache = [[inf for _ in range(1 << m)] for _ in range(n + 1)]
        cache[0][0] = 0
        for i in range(1, n+1):
            for mask in range(1 << m):
                for j in range(m):
                    if mask & (1 << j):
                        cache[i][mask] = min(
                            cache[i][mask], cache[i][mask & ~(1 << j)] + cost[i - 1][j])
                        cache[i][mask] = min(
                            cache[i][mask], cache[i - 1][mask] + cost[i - 1][j])
                        cache[i][mask] = min(
                            cache[i][mask], cache[i - 1][mask & ~(1 << j)] + cost[i - 1][j])
        return cache[n][(1 << m) - 1]

题解 3 - rust

• 编辑时间：2023-06-20
• 执行用时：16ms
• 内存消耗：2.3MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn connect_two_groups(cost: Vec<Vec<i32>>) -> i32 {
        let n = cost.len();
        let m = cost[0].len();
        let mut cache = vec![vec![0x3f3f3f3f; 1 << m]; n + 1];
        cache[0][0] = 0;
        for i in 1..=n {
            for mask in 0..(1 << m) {
                for j in 0..m {
                    if (mask & (1 << j)) != 0 {
                        cache[i][mask] = cache[i][mask]
                            .min(cache[i][mask & !(1 << j)] + cost[i - 1][j])
                            .min(cache[i - 1][mask] + cost[i - 1][j])
                            .min(cache[i - 1][mask & !(1 << j)] + cost[i - 1][j]);
                    }
                }
            }
        }
        return cache[n][(1 << m) - 1];
    }
}