265. Paint House II

[LLancelot]

[LLancelot]

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        if not costs:
            return 0
        if len(costs) == 1:
            return min(costs[0])

        for i_house in range(1, len(costs)):
            for j_color in range(len(costs[0])):
                costs[i_house][j_color] = min(costs[i_house-1][:j_color]+costs[i_house-1][j_color+1:]) + costs[i_house][j_color]
        return min(costs[-1])

[LLancelot]

class Solution:
    def minCostII(self, cost):
        res, res1=[-1, 0], [-1, 0]
        for x in cost:
            m1, m2 = float('Inf'), float('Inf')
            p1, p2 = -1, -1
            for i, y in enumerate(x):
                if y<m1:
                    m1, m2=y, m1
                    p1, p2=i, p1
                elif y<m2:
                    m2=y
                    p2=i
            if res[0]!=p1 and res[0]!=p2:
                res[1], res1[1]=res[1]+m1, res[1]+m2
                res[0], res1[0]=p1, p2
            elif res[0]==p1:
                res[1], res1[1]=res[1]+m2, res1[1]+m1
                res[0], res1[0]=p2, p1
                if res[1]>res1[1]:
                    res, res1 =res1, res
            else:
                res[1], res1[1] = res[1] + m1, res1[1] + m2
                res[0], res1[0] = p1, p2
        return res[1]

[[14,18,16],[18,4,9],[2,20,2],[4,19,10],[7,13,4],[11,4,17],[10,11,20],[8,3,16],[4,17,15],[8,7,3],[1,19,4],[12,11,18],[10,5,6],[14,19,19],[5,8,12],[12,16,13],[20,8,16],[17,15,2],[14,2,20],[2,6,14],[3,17,17],[17,8,3],[16,8,4],[7,14,8],[13,3,7],[15,11,14],[19,20,10],[4,2,6]]

[LLancelot]

88ms 答案：

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        n = len(costs)
        if n == 0: return 0 # This is a valid case.
        k = len(costs[0])

        # Firstly, we need to determine the 2 lowest costs of
        # the first row. We also need to remember the color of
        # the lowest.
        prev_min_cost = prev_second_min_cost = prev_min_color = None
        for color, cost in enumerate(costs[0]):
            if prev_min_cost is None or cost < prev_min_cost:
                prev_second_min_cost = prev_min_cost
                prev_min_color = color
                prev_min_cost = cost
            elif prev_second_min_cost is None or cost < prev_second_min_cost:
                prev_second_min_cost = cost

        # And now, we need to work our way down, keeping track of the minimums.
        for house in range(1, n):
            min_cost = second_min_cost = min_color = None
            for color in range(k):
                # Determime cost for this cell (without writing it into input array.)
                cost = costs[house][color]
                if color == prev_min_color:
                    cost += prev_second_min_cost
                else:
                    cost += prev_min_cost
                # And work out whether or not it is a current minimum.
                if min_cost is None or cost < min_cost:
                    second_min_cost = min_cost
                    min_color = color
                    min_cost = cost
                elif second_min_cost is None or cost < second_min_cost:
                    second_min_cost = cost
            # Transfer currents to be prevs.
            prev_min_cost = min_cost
            prev_min_color = min_color
            prev_second_min_cost = second_min_cost

        return prev_min_cost

[ytp327]

class Solution:
    def minCost(self, cost):
        res=[[-1, 0], [-1, 0]]
        for x in cost:
            curRes=[[-1,float('Inf')], [-1,float('Inf')]]
            for i, y in enumerate(x):
                if i!=res[0][0]:
                    temp=y+res[0][1]
                else:
                    temp=y+res[1][1]
                if temp<curRes[0][1]:
                    curRes[1]=curRes[0]
                    curRes[0]=[i,temp]
                elif temp<curRes[1][1]:
                    curRes[1]=[i,temp]
            res=curRes
        return res[0][1]