1595。连接两组点的最低成本
难度：难
主题：数组、动态规划、位操作、矩阵、位掩码
给你两组点，第一组有大小1点，第二组有大小2点，大小1 >=尺寸2.
任意两点之间的连接成本以大小 1 x size2 矩阵给出，其中 cost[i][j] 是连接点 i 的成本第一组和第二组的 j 点。如果两个组中的每个点都连接到相反组中的一个或多个点，则这些组已连接。换句话说，第一组中的每个点必须连接到第二组中的至少一个点，第二组中的每个点必须连接到第一组中的至少一个点。
返回连接两个组所需的最低成本。
示例1：
- 输入： 成本 = [[15, 96], [36, 2]]
- 输出： 17
- 说明：连接组的最佳方式是：
1--a 2--b this results in a total cost of 17.
示例2：
- 输入： 成本 = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
- 输出： 4
- 说明：连接组的最佳方式是：
1--a 2--b 2--c 3--a this results in a total cost of 4.
请注意，有多个点连接到第一组中的点 2 和第二组中的点 a。这并不重要，因为可以连接的点数没有限制。我们只关心最低的总成本。
示例 3：
- 输入： 成本 = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
- 输出： 10
约束：
- 大小1 == cost.length
- 大小2 == 成本[i].长度
- 1 <= 大小1，大小2 <= 12
- 大小1 >=大小2
- 0 <= 成本[i][j] <= 100
提示：
- 左侧的每个点要么连接到已连接到某个左侧节点的精确点，要么连接到右侧未连接到任何节点的节点的子集
- 使用带有位掩码的动态规划，其中状态将为（第一组中分配的点的数量，第二组中分配的点的位掩码）。
解决方案：
我们可以利用带有位掩码的动态编程。这个想法是通过考虑第一组中的每个点并尝试将其连接到第二组中的所有点来最小化成本。
具有位掩码的动态规划 (dp) 方法
步骤：
-
国家代表：
- 使用 dp 表 dp[i][mask]，其中：
- i 是第一组中的索引（范围从 0 到 size1-1）。
- mask 是一个位掩码，表示第二组中的哪些点已连接。
- 使用 dp 表 dp[i][mask]，其中：
-
状态转换:
- 对于第一组中的每个点，尝试将其连接到第二组中的每个点，相应地更新 dp 表。
- 如果连接了第二组中的新点，则更新掩码中的相应位。
-
基本案例：
- 从 dp[0][0] = 0 开始（最初没有连接）。
-
目标：
- 计算 dp[size1][(1 << size2) - 1] 的最小成本，它表示连接两组中的所有点。
让我们用 php 实现这个解决方案：1595。连接两组点的最低成本
<?php
/**
* @param Integer[][] $cost
* @return Integer
*/
function connectTwoGroups($cost) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example usage:
$cost1 = [[15, 96], [36, 2]];
$cost2 = [[1, 3, 5], [4, 1, 1], [1, 5, 3]];
$cost3 = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]];
echo connectTwoGroups($cost1) . "\n"; // Output: 17
echo connectTwoGroups($cost2) . "\n"; // Output: 4
echo connectTwoGroups($cost3) . "\n"; // Output: 10
?>
解释：
- dp 数组 dp[i][mask] 存储将第 1 组中的前 i 个点与第 2 组中的点连接起来的最小成本，如 mask 所示。
- 嵌套循环迭代 i 和 mask 的每个组合，尝试通过考虑所有可能的连接来找到最佳成本。
- 最终，该解决方案会考虑第二组中某些点可能仍未连接的情况来计算最小成本，确保所有点都已连接。
这种方法有效地处理了问题的约束，并确保连接两个组的成本最小。
联系链接
如果您发现本系列有帮助，请考虑在 github 上给存储库 一颗星，或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大！
如果您想要更多类似的有用内容，请随时关注我：
- 领英
- github
