commit 614eb2fe68188f715ccf978e1b3dd28d08088cfc
parent 9dbc3c5dce097240f12c2f0a4a805bcae5d80098
Author: Jack Sangdahl <jack@pngu.org>
Date: Sun, 11 Jan 2026 22:46:13 -0700
1595. minimum cost to connect two groups of points
Diffstat:
2 files changed, 126 insertions(+), 0 deletions(-)
diff --git a/min_cost_connect_two_group.c b/min_cost_connect_two_group.c
@@ -0,0 +1,77 @@
+// 1595. Minimum Cost to Connect Two Groups of Points
+#include "leetcode.h"
+
+/*
+ * you are given two groups of points where the first group has 'size_i' points,
+ * the second group has 'size_j' points, and 'size_i >= size_j'. the 'cost' of
+ * the connection between any two points are giveen in 'size_i * size_j' 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 oint 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 pooint
+ * in the second group. return the minimum cost it takes to connect the two
+ * groups.
+ */
+
+int connectTwoGroups(int **cost, int costSize, int *costColSize) {
+ int n = costSize, m = costColSize[0];
+ int *dp0 = (int *)malloc((1 << m) * sizeof(int));
+ for (int i = 0; i < (1 << m); i++)
+ dp0[i] = INT_MAX;
+ dp0[0] = 0;
+ for (int i = 0; i < n; ++i) {
+ int *dp1 = (int *)malloc((1 << m) * sizeof(int));
+ for (int j = 0; j < (1 << m); j++)
+ dp1[i] = INT_MAX;
+ for (int j = 0; j < (1 << m); ++j) {
+ for (int k = j;; k = (k - 1) & j) {
+ int total = 0;
+ if (j == k) {
+ total = INT_MAX;
+ for (int l = 0; l < m; ++l)
+ if (k & (1 << l))
+ total = fmin(total, cost[i][l]);
+ } else {
+ for (int l = 0; l < m; ++l) {
+ if (k & (1 << l)) {
+ if (!(j & (1 << l))) {
+ total = INT_MAX;
+ break;
+ }
+ } else if (j & (1 << l))
+ total += cost[i][l];
+ }
+ }
+ dp1[j] = fmin(dp1[j], dp0[k] + total);
+ if (!k)
+ break;
+ }
+ }
+ memcpy(dp0, dp1, (1 << m) * sizeof(int));
+ free(dp1);
+ }
+ int ans = dp0[(1 << m) - 1];
+ free(dp0);
+ return ans;
+}
+
+int main() {
+ int c1i[2][2] = {{15, 96}, {36, 2}};
+ int c2i[3][3] = {{1, 3, 5}, {4, 1, 1}, {1, 5, 3}};
+ int c3i[5][3] = {{2, 5, 1}, {3, 4, 7}, {8, 1, 2}, {6, 2, 4}, {3, 8, 8}};
+ struct two_d_arr *c1 =
+ two_d_arr_init(ARRAY_SIZE(c1i), ARRAY_SIZE(c1i[0]), c1i);
+ struct two_d_arr *c2 =
+ two_d_arr_init(ARRAY_SIZE(c2i), ARRAY_SIZE(c2i[0]), c2i);
+ struct two_d_arr *c3 =
+ two_d_arr_init(ARRAY_SIZE(c3i), ARRAY_SIZE(c3i[0]), c3i);
+ printf("%d\n",
+ connectTwoGroups(c1->arr, c1->row_size, c1->col_size)); // expect: 17
+ printf("%d\n",
+ connectTwoGroups(c2->arr, c2->row_size, c2->col_size)); // expect: 4
+ printf("%d\n",
+ connectTwoGroups(c3->arr, c3->row_size, c3->col_size)); // expect: 10
+ two_d_arr_free(c1);
+ two_d_arr_free(c2);
+ two_d_arr_free(c3);
+}
diff --git a/min_cost_connect_two_group.py b/min_cost_connect_two_group.py
@@ -0,0 +1,49 @@
+# 1595. Minimum Cost to Connect Two Groups of Points
+from functools import lru_cache
+
+"""
+you are given two groups of points where the first group has 'size_i' points,
+the second group has 'size_j' points, and 'size_i >= size_j'. the 'cost' of
+the connection between any two points are giveen in 'size_i size_j' 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 oint 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 pooint
+in the second group. return the minimum cost it takes to connect the two
+groups.
+"""
+
+
+class Solution(object):
+ def connectTwoGroups(self, cost):
+ """
+ :type cost: List[List[int]]
+ :rtype: int
+ """
+ n, m = len(cost), len(cost[0])
+ smallest = [min([cost[i][j] for i in range(n)]) for j in range(m)]
+
+ @lru_cache(None)
+ def dfs(i, mask):
+ res = 0 if i >= n else float("inf")
+ if i >= n:
+ for j in range(m):
+ if mask & (1 << j) == 0:
+ res += smallest[j]
+ else:
+ for j in range(m):
+ res = min(res, cost[i][j] + dfs(i + 1, mask | (1 << j)))
+ return res
+
+ return dfs(0, 0)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.connectTwoGroups(cost=[[15, 96], [36, 2]]))
+ print(obj.connectTwoGroups(cost=[[1, 3, 5], [4, 1, 1], [1, 5, 3]]))
+ print(
+ obj.connectTwoGroups(
+ cost=[[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
+ )
+ )
