Minimum Cost to Connect Two Groups of Points LeetCode solution in Python

1
class Solution:
2
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
3
        m, n = len(cost), len(cost[0])
4
        mn = [min(x) for x in zip(*cost)]  # min cost of connecting points in 2nd group
5

6
        @lru_cache(None)
7
        def fn(i, mask):
8
            """Return min cost of connecting group1[i:] and group2 represented as mask."""
9
            if i == m:
10
                return sum(mn[j] for j in range(n) if not (mask & (1 << j)))
11
            return min(cost[i][j] + fn(i + 1, mask | 1 << j) for j in range(n))
12

13
        return fn(0, 0)