Участник:ArtemTovkes/minimum-cost-to-connect-two-groups-of-points

Материал из DISCOPAL
< Участник:ArtemTovkes
Версия от 08:31, 22 декабря 2020; StasFomin (обсуждение | вклад) (StasFomin переименовал страницу Участник:ArtemTovke/minimum-cost-to-connect-two-groups-of-points в Участник:ArtemTovkes/minimum-cost-to-connect-two-groups-of-points без оставления перенап…)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Python 3 https://leetcode.com/problems/minimum-cost-to-connect-two-groups-of-points/

class Solution:
    def connectTwoGroups(self, cost):
        m, n = len(cost), 1 << len(cost[0])
        c = [[self.computeCost(cur, cost[i]) for cur in range(n)] for i in range(m)]
        dp0 = [self.computeCost(cur, cost[0]) for cur in range(n)]
        mn = [min(c) for c in cost]
        for i in range(1, m):
            dp1 = [sys.maxsize] * n
            for cur in range(1, n):
                subset = cur
                while subset:
                    val = c[i][subset]
                    dp1[cur] = min(dp1[cur], dp0[cur ^ subset] + val)
                    subset = (subset - 1) & cur
                dp1[cur] = min(dp1[cur], dp0[cur] + mn[i])
            dp0, dp1 = dp1, dp0
        return dp0[-1]
 
    def computeCost(self, subset, costs):
        if subset == 0:
            return sys.maxsize
        res = 0
        for j in range(len(costs)):
            if subset & (1 << j):
                res += costs[j]
        return res