```
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[0])
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.