算法leetcode

【DP难题】力扣1595-连通两组点的最小成本

字数统计: 1.1k字   |   阅读时长: 4分
, , ,

摘要: 力扣 1595，比较难的图论题，抽象之后是最小边覆盖问题，有状态压缩DP和二分图最大匹配两种解法。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

今天我们来看一个比较难的图论题，力扣 1575，也就是第 207 周赛 D 题。抽象之后是带权最小边覆盖问题，有状态压缩 DP 和二分图最大权匹配两种解法。本文主要看一下状态压缩 DP 的解法，二分图最大权匹配比较难，以后再学习。

$1 题目

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

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

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

提示：

1
2
3
4
5
size1 == cost.length
size2 == cost[i].length
1 <= size1, size2 <= 12
size1 >= size2
0 <= cost[i][j] <= 100

示例 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

$2 题解

算法1: 状态压缩DP

用状态压缩 DP 的话，本题是一个非常经典的问题，关于状态压缩 DP，可以参考下面这篇文章：

问题等价于在一个矩阵中选数, 每一行和每一列都至少有一个元素被选中, 同时选中元素的和最小。算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
状态定义：
dp[i][s] := 第一组点选了前 i 个，第二组点的选择情况为 s 时的最小成本

答案：
dp[s1 - 1][(1 << s2) - 1]

初始化：
dp[0][1 << j] = cost[0][j], 0 <= j <= s2 - 1

转移：
(s >> j & 1) == 0: 左边选 i 右边选一个不在 j 中的点，有两个方向可以转移过来
    dp[i][s | (1 << j)] = dp[i - 1][s] + cost[i][j]    j not in s
    dp[i][s | (1 << j)] = dp[i][s] + cost[i][j]    j not in s
(s >> j & 1) == 0: 左边选 i 右边选一个在 j 中的点，只有一个方向可以转移过来
    dp[i][s] = dp[i - 1][s] + cost[i][j]   j in s

代码 (C++)

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
class Solution {
public:
    int connectTwoGroups(vector<vector<int>>& cost) {
        int n = cost.size(), m = cost[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(1 << m, INT_MAX / 2));
        dp[0][0] = 0;
        for(int i = 1; i <= n; ++i)
        {
            for(int state = 0; state < (1 << m); ++state)
            {
                for(int j = 0; j < m; ++j)
                {
                    if((state >> j & 1) == 0)
                    {
                        dp[i][state | (1 << j)] = min(dp[i][state | (1 << j)], dp[i - 1][state] + cost[i - 1][j]);
                        dp[i][state | (1 << j)] = min(dp[i][state | (1 << j)], dp[i][state] + cost[i - 1][j]);
                    }
                    else
                    {
                        dp[i][state] = min(dp[i][state], dp[i - 1][state] + cost[i - 1][j]);
                    }
                }
            }
        }
        return dp[n][(1 << m) - 1];
    }
};

算法2: 转换为二分图最大权匹配

这个解法有点难，并且在面试中是超纲的。如果是力扣春秋季赛，可能会有点用，以后有时间可以详细拆解一下，本文大家重点掌握状态压缩DP即可。

Ref: 题解

Share