Paint House II

Problem: Paint House II

The solution is like the previous one. The real O(nk) solution is here. The general idea is to just store 2 smallest cost at previous step. If one of the cost is based on the same color, we just choose the other one.

Code in Python:

class Solution(object):
    def minCostII(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        if not costs: return 0
        for i in xrange(1, len(costs)):
            for j in xrange(len(costs[0])):
                costs[i][j] += min(costs[i-1][:j] + costs[i-1][j+1:])
        return min(costs[-1])