class Solution(object): def minCostII(self, costs): """ :type costs: List[List[int]] :rtype: int """ if not costs: return 0 n, k = len(costs), len(costs) for i in xrange(1, n): min1 = min(costs[i-1]) idx = costs[i-1].index(min1) min2 = min(costs[i-1][:idx] + costs[i-1][idx+1:]) for j in xrange(k): if j == idx: costs[i][j] += min2 else: costs[i][j] += min1 return min(costs[-1])
This is a Markov Chain (dp) with k states
(color 1, color 2...color k) and n stages, we simply update the
costs matrix to keep track of the optimal value for each state at current stage.
min1 means we paint all other states with the minimum cost, while
min2 means we cannot paint consecutive houses with same color so we choose the second lowest cost to add up with.