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

  |  

摘要: 力扣 1575,比较难的图论题,抽象之后是最小边覆盖问题,有状态压缩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:
输入: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