265. Paint House II

[moyuanhuang]

https://leetcode.com/problems/paint-house-ii/

Tips: 直觉DP，注意其实对于房子i，只需要知道刷到房子i-1为止最少和第二少的cost就足够了，因为你刷房子i的时候总会想挑之前最小的。

class Solution:
    def minCostII(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        # We just need (lowest_cost, lowest_color) and second_lowest_cost from the previous house!!!
        n_houses = len(costs)
        if n_houses == 0:
            return 0

        n_colors = len(costs[0])

        for i in range(1, n_houses):
            optimal = min(costs[i - 1])
            index = costs[i - 1].index(optimal)
            sub_optimal = min(costs[i - 1][:index] + costs[i - 1][index + 1:])

            for j in range(n_colors):
                if j == index:
                    costs[i][j] += sub_optimal
                else:
                    costs[i][j] += optimal

        return min(costs[n_houses - 1])