1595. Minimum Cost to Connect Two Groups of Points
Difficulty: Hard
Topics: Array
, Dynamic Programming
, Bit Manipulation
, Matrix
, Bitmask
You are given two groups of points where the first group has size1
points, the second group has size2
points, and size1 >= size2
.
The cost
of the connection between any two points are given in an size1 x size2
matrix where cost[i][j]
is the cost of connecting point i
of the first group and point j
of the second group. The groups are connected if each point in both groups is connected to one or more points in the opposite group. In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group.
Return the minimum cost it takes to connect the two groups.
Example 1:
- Input: cost = [[15, 96], [36, 2]]
- Output: 17
- Explanation: The optimal way of connecting the groups is:
1--A
2--B
This results in a total cost of 17.
Example 2:
- Input: cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
- Output: 4
- Explanation: The optimal way of connecting the groups is:
1--A
2--B
2--C
3--A
This results in a total cost of 4.
Note that there are multiple points connected to point 2 in the first group and point A in the second group. This does not matter as there is no limit to the number of points that can be connected. We only care about the minimum total cost.
Example 3:
- Input: cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
- Output: 10
Constraints:
size1 == cost.length
size2 == cost[i].length
1 <= size1, size2 <= 12
size1 >= size2
0 <= cost[i][j] <= 100
Hint:
- Each point on the left would either be connected to exactly point already connected to some left node, or a subset of the nodes on the right which are not connected to any node
- Use dynamic programming with bitmasking, where the state will be (number of points assigned in first group, bitmask of points assigned in second group).
Solution:
We can leverage dynamic programming with bitmasking. The idea is to minimize the cost by considering each point in the first group and trying to connect it to all points in the second group.
Dynamic Programming (DP) Approach with Bitmasking
Steps:
-
State Representation:
- Use a DP table
dp[i][mask]
where:-
i
is the index in the first group (ranging from0
tosize1-1
). -
mask
is a bitmask representing which points in the second group have been connected.
-
- Use a DP table
-
State Transition:
- For each point in the first group, try connecting it to every point in the second group, updating the DP table accordingly.
- If a new point in the second group is connected, update the corresponding bit in the mask.
-
Base Case:
- Start with
dp[0][0] = 0
(no connections initially).
- Start with
-
Goal:
- Compute the minimum cost for
dp[size1][(1 << size2) - 1]
, which represents connecting all points from both groups.
- Compute the minimum cost for
Let's implement this solution in PHP: 1595. Minimum Cost to Connect Two Groups of Points
<?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
?>
Explanation:
- The DP array
dp[i][mask]
stores the minimum cost to connect the firsti
points from group 1 with the points in group 2 as indicated bymask
. - The nested loops iterate over each combination of
i
andmask
, trying to find the optimal cost by considering all possible connections. - In the end, the solution calculates the minimum cost considering the scenarios where some points in the second group may still be unconnected, ensuring all points are connected.
This approach efficiently handles the problem's constraints and ensures the minimum cost for connecting the two groups.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)